Synthesis of quantum-logic circuits

By Vivek V. Shende, Stephen S. Bullock, Igor L. Markov. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2004

851 citations recorded by the source corpus.

The pressure of fundamental limits on classical computation and the promise of exponential speedups from quantum effects have recently brought quantum circuits (Proc. R. Soc. Lond. A, Math. Phys. Sci., vol. 425, p. 73, 1989) to the attention of the electronic design automation community (Proc. 40th ACM/IEEE Design Automation Conf., 2003), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 68, p. 012318, 2003), (Proc. 41st Design Automation Conf., 2004), (Proc. 39th Design Automation Conf., 2002), (Proc. Design, Automation, and Test Eur., 2004), (Phys. Rev. A, At. Mol. Opt. Phy., vol. 69, p. 062321, 2004), (IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 22, p. 710, 2003). Efficient quantum-logic circuits that perform two tasks are discussed: 1) implementing generic quantum computations, and 2) initializing quantum registers. In contrast to conventional computing, the latter task is nontrivial because the state space of an n-qubit register is not finite and contains exponential superpositions of classical bitstrings. The proposed circuits are asymptotically optimal for respective tasks and improve earlier published results by at least a factor of 2. The circuits for generic quantum computation constructed by the algorithms are the most efficient known today in terms of the number of most expensive gates [quantum controlled-NOTs (CNOTs)]. They are based on an analog of the Shannon decomposition of Boolean functions and a new circuit block, called quantum multiplexor (QMUX), which generalizes several known constructions. A theoretical lower bound implies that the circuits cannot be improved by more than a factor of 2. It is additionally shown how to accommodate the severe architectural limitation of using only nearest neighbor gates, which is representative of current implementation technologies. This increases the number of gates by almost an order of magnitude, but preserves the asymptotic optimality of gate counts

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/579a4e227ad2ff319ec200ac9c960622f0f12a28

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Low-Depth Quantum Simulation of Materials (2017, background): “[88] would allow one to implement PREPAREðWÞ at gate complexity P ∈ 2OðlogLÞ ∈ OðN2Þ.”
Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision (2015, methodology): “Then we use O ( K ) gates to prepare the corresponding superposition over | k [SBM06, Sec IV].”
Hamiltonian Simulation in the Interaction Picture (2018, methodology): “[20] Vivek V Shende, Stephen S Bullock, and Igor L Markov.”
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters (2015, neutral): “With this choice, we have the following error bound, proved in the Appendix.”
Variational quantum algorithms for nonlinear problems (2019, background): “An upper bound for the depth of the resulting quantum circuit is d> ≤ 9n[(23/48)(2χ)2 + 4/3] [64].”
Efficient quantum algorithm for dissipative nonlinear differential equations (2020, neutral): “, perform a unitary transform mapping |0〉|0〉 7→ |φint〉) in time complexity O(m) [48] using the known values of ‖uin‖ and ‖b((k − 1)h)‖.”
Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity (2018, neutral): “[69]), which requires a number of T gates scaling as O ( L log ð L= ϵ Þ ) .”
Toward the first quantum simulation with quantum speedup (2017, neutral): “outine maps |0i into the state PL l=1 √ αl|li, where {αl}L l=1 are the coeﬃcients of terms in the target Hamiltonian. This is accomplished through the generic state preparation algorithm described in [69]. The second state preparation subroutine generates a state proportional to PK k=0 p tk/k!|1k0K−”
Quantum Generative Adversarial Networks for learning and loading random distributions (2019, background): “But, the exact preparation of a generic state in n qubits requires O (2) gates [6–9].”
Qudits and High-Dimensional Quantum Computing (2020, background): “(102) Note that the function of the controlled operation CUd t−l can be considered as a “quantum multiplexer” [24, 87, 139].”
Option Pricing using Quantum Computers (2019, positive): “For n = 2, this operation can be efficiently implemented using four CNOT gates and four single qubit Y-rotations [45, 46].”