Asymptotically optimal quantum circuits for d-level systems -: art. no. 230502
Asymptotically optimal quantum circuits for d-level systems -: art. no. 230502
复制标题
DOI：
10.1103/physrevlett.94.230502
复制
发表时间：
2005-06-17
影响因子：
8.6
通讯作者：
Brennen, GK
中科院分区：
文献类型：
--
作者：
Bullock, SS;O'Leary, DP;Brennen, GK
量子计算的可扩展性要求在多个子系统上处理信息。然而，目前还不清楚量子算法的复杂性（由纠缠门的数量量化）如何取决于子系统的大小。我们研究了量子电路的复杂性，在许多d-能级系统（qudits）上进行精确的通用计算。两个qudit门的数量上的一个下界和一个建设性的上界的结果，证明了一个尖锐的渐近Theta（d（2n））门。这就解决了所有d-能级系统（d有限）的复杂性问题。最优渐近适用于具有局部约束的系统，例如，最近邻的相互作用
Scalability of a quantum computation requires that the information be processed on multiple subsystems. However, it is unclear how the complexity of a quantum algorithm, quantified by the number of entangling gates, depends on the subsystem size. We examine the quantum circuit complexity for exactly universal computation on many d-level systems (qudits). Both a lower bound and a constructive upper bound on the number of two-qudit gates result, proving a sharp asymptotic of Theta(d(2n)) gates. This closes the complexity question for all d-level systems (d finite). The optimal asymptotic applies to systems with locality constraints, e.g., nearest neighbor interactions.