The DOI matches its Crossref record; 43 of the 43 references it cites were found in a registry or an index.
Synthesis of quantum-logic circuits
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
Quantum Computation and Quantum Information
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895
Quantum computation and quantum information
Law, J. (2001) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/505482.505499 · Cited by 18,842
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Quantum cryptography: Public key distribution and coin tossing
Bennett, C. H., & Brassard, G. (2014) · Theoretical Computer Science · doi:10.1016/j.tcs.2014.05.025 · Cited by 8,299
Quantum cryptography: Public key distribution and coin tossing
Bennett, C. H., & Brassard, G. (2020) · arXiv · doi:10.48550/arxiv.2003.06557 · Cited by 8,299
Elementary gates for quantum computation
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306 · cited 1×
“, Shor’s factorization algorithm [29] or Grover’s quantum se arch [16]), but have long been known to be possible for arbitrary quantum functions [12, 3].”
Feynman, R. P. (1986) · Foundations of Physics · doi:10.1007/bf01886518 · Cited by 1,770
Quantum computational networks
Deutsch, D. E. (1989) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1989.0099 · Cited by 1,270 · cited 1×
“The problem has been known for some time in quantum computing, and it was considered in [12], [21], and [27] after the original formulation [11] of the quantum-circuit model.”
Two-bit gates are universal for quantum computation
DiVincenzo, D. P. (1995) · Physical Review A · doi:10.1103/physreva.51.1015 · Cited by 1,069
On the role of entanglement in quantum-computational speed-up
Jozsa, R., & Linden, N. (2003) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2002.1097 · Cited by 839
Synthesis of reversible logic circuits
Shende, V. V., Prasad, A. K., Markov, I. L., & Hayes, J. P. (2003) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2003.811448 · Cited by 568
Self-citationLimits to binary logic switch scaling-a gedanken model
Zhirnov, V. V., Cavin, R. K., Hutchby, J. A., & Bourianoff, G. I. (2003) · Proceedings of the IEEE · doi:10.1109/jproc.2003.818324 · Cited by 482
Optimal quantum circuits for general two-qubit gates
Vatan, F., & Williams, C. (2004) · Physical Review A · doi:10.1103/physreva.69.032315 · Cited by 443 · cited 4×
“while three CNOT gates are necessary and sufficient in the worst case [28], [29], [35], [36].”
InfluentialQuantum Circuits for General Multiqubit Gates
Möttönen, M., Vartiainen, J. J., Bergholm, V., & Salomaa, M. M. (2004) · Physical Review Letters · doi:10.1103/physrevlett.93.130502 · Cited by 390
Universality in quantum computation
Deutsch, D. E., Barenco, A., & Ekert, A. (1995) · Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences · doi:10.1098/rspa.1995.0065 · Cited by 346
Universality in Quantum Computation
Deutsch, D., Barenco, A., & EKERT, A. K. (1995) · CERN Document Server (European Organization for Nuclear Research) · Cited by 322
Minimal universal two-qubit controlled-NOT-based circuits
Shende, V. V., Markov, I. L., & Bullock, S. S. (2004) · Physical Review A · doi:10.1103/physreva.69.062321 · Cited by 288
Self-citationUniversal quantum circuit for two-qubit transformations with three controlled-NOT gates
Vidal, G., & Dawson, C. M. (2004) · Physical Review A · doi:10.1103/physreva.69.010301 · Cited by 277
Efficient Decomposition of Quantum Gates
Vartiainen, J. J., Möttönen, M., & Salomaa, M. M. (2004) · Physical Review Letters · doi:10.1103/physrevlett.92.177902 · Cited by 240
Implementation of Shor's algorithm on a linear nearest neighbour qubit array
Fowler, A. G., Devitt, S. J., & Hollenberg, L. C. L. (2004) · Quantum Information and Computation · doi:10.26421/qic4.4-1 · Cited by 194
Transformation rules for designing CNOT-based quantum circuits
Iwama, K., Kambayashi, Y., & Yamashita, S. (2002) · Proceedings of the 39th conference on Design automation - DAC '02 · doi:10.1145/513918.514026 · Cited by 164
Implementation of Shor's algorithm on a linear nearest neighbour qubit array
Fowler, A. G., Devitt, S. J., & Hollenberg, L. C. L. (2004) · CERN Document Server (European Organization for Nuclear Research) · doi:10.5555/2011827.2011828 · Cited by 139
Approximation by Quantum Circuits
Knill, E. (1995) · arXiv · doi:10.48550/arxiv.quant-ph/9508006 · Cited by 136
Reducing quantum computations to elementary unitary operations
Cybenko, G. V. (2001) · Computing in Science & Engineering · doi:10.1109/5992.908999 · Cited by 95
Exact Two-Qubit Universal Quantum Circuit
Zhang, J., Vala, J., Sastry, S., & Whaley, K. B. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.027903 · Cited by 93
Quantum logic synthesis by symbolic reachability analysis
Hung, W. N. N., Song, X., Yang, G., Yang, J. S., & Perkowski, M. A. (2004) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1145/996566.996790 · Cited by 91
Quantum circuits for incompletely specified two-qubit operators
Shende, V., & Markov, I. L. (2005) · Quantum Information and Computation · doi:10.26421/qic5.1-5 · Cited by 67
Self-citationBuilding quantum wires: the long and the short of it
Oskin, M., Chong, F. T., Chuang, I. L., & Kubiatowicz, J. D. (2003) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/859618.859661 · Cited by 66
Recognizing small-circuit structure in two-qubit operators
Shende, V., Bullock, S. S., & Markov, I. L. (2004) · Physical Review A · doi:10.1103/physreva.70.012310 · Cited by 64
Self-citationArbitrary two-qubit computation in 23 elementary gates
Bullock, S. S., & Markov, I. L. (2003) · Physical Review A · doi:10.1103/physreva.68.012318 · Cited by 59
Self-citationA Rudimentary Quantum CompilerPreprint
Tucci, R. R. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9805015 · Cited by 52
Realization of a General Three-Qubit Quantum GatePreprint
Vatan, F., & Williams, C. P. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0401178 · Cited by 50
Transformation rules for designing CNOT-based quantum circuits
Iwama, K., Kambayashi, Y., & Yamashita, S. (2002) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1109/dac.2002.1012662 · Cited by 50
Quantum-computer architecture using nonlocal interactions
Brennen, G. K., Song, D., & Williams, C. J. (2003) · Physical Review A · doi:10.1103/physreva.67.050302 · Cited by 47
Asymptotically optimal circuits for arbitrary n-qubit diagonal comutations
Bullock, S. S., & Markov, I. L. (2004) · Quantum Information and Computation · doi:10.5555/2011572.2011575 · Cited by 46
Self-citationSmaller Circuits for Arbitrary n-qubit Diagonal ComputationsPreprint
Bullock, S. S., & Markov, I. L. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0303039 · Cited by 38
Self-citationCompiling Quantum Circuits using the Palindrome TransformPreprint
Aho, A. V., & Svore, K. M. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0311008 · Cited by 31
Note on the Khaneja Glaser decomposition
Bullock, S. S. (2004) · Quantum Information and Computation · doi:10.26421/qic4.5-5 · Cited by 25
Self-citationSmaller two-qubit circuits for quantum communication and computation
Shende, V., Markov, I. L., & Bullock, S. S. (2004) · Design, Automation, and Test in Europe · doi:10.1109/date.2004.1269020 · Cited by 24
Self-citationSmaller two-qubit circuits for quantum communication and computation
Shende, V., Markov, I. L., & Bullock, S. S. (2004) · Design, Automation, and Test in Europe · doi:10.5555/968879.969163 · Cited by 17
Self-citationBuilding quantum wires: the long and the short of it
Oskin, M., Chong, F. T., Chuang, I. L., & Kubiatowicz, J. D. (2004) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca.2003.1207015 · Cited by 17
Cited by
Simulating Hamiltonian Dynamics with a Truncated Taylor Series
Berry, D. W., Childs, A. M., Cleve, R., Kothari, R., & Somma, R. D. (2015) · Physical Review Letters · doi:10.1103/physrevlett.114.090502 · Cited by 742
Childs, A. M., Kothari, R., & Somma, R. D. (2017) · SIAM Journal on Computing · doi:10.1137/16m1087072 · Cited by 646
“Then we use O ( K ) gates to prepare the corresponding superposition over | k [SBM06, Sec IV].”
BackgroundMethodToward the first quantum simulation with quantum speedup
Childs, A. M., Maslov, D., Nam, Y., Ross, N. J., & Su, Y. (2018) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1801723115 · Cited by 551
Quantum autoencoders for efficient compression of quantum data
Romero, J., Olson, J. P., & Aspuru-Guzik, A. (2017) · Quantum Science and Technology · doi:10.1088/2058-9565/aa8072 · Cited by 559
Qudits and High-Dimensional Quantum Computing
Wang, Y., Hu, Z., Sanders, B. C., & Kais, S. (2020) · Frontiers in Physics · doi:10.3389/fphy.2020.589504 · Cited by 478
Metadata
- Authors
- Shende, V. V., Bullock, S. S., & Markov, I. L.
- Venue
- IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Published
- 2006-06
- Volume
- 25
- Issue
- 6
- Pages
- 1000-1010
- ISSN
- 0278-0070 (ISSN-L)
- 1937-4151
- OpenAlex
- W2104590612
- Cited by
- 669
- References
- 43
- FWCI
- 16.46
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.