Rapid solution of problems by quantum computation
Abstract
A class of problems is described which can be solved more efficiently by quantum computation than by any classical or stochastic method. The quantum computation solves the problem with certainty in exponentially less time than any classical deterministic computation.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The Deutsch-Jozsa algorithm is among the first examples to demonstrate that a quantum algorithm can achieve exponential speedup over any possible deterministic classical algorithms.
“This algorithm is among the irst examples to demonstrate that a quantum algorithm can achieve exponentially speedup over any possible deterministic classical algorithms.”
From QASMBench: A Low-Level Quantum Benchmark Suite for NISQ Evaluation and Simulation (2023) · cites this paper as [33]
The Deutsch-Jozsa algorithm can get the answer with only one-time evaluation to the oracle function whereas a deterministic classical computer would require 2^{n-1}+1 evaluations.
“the quantum computer can get the answer with only one-time evaluation to the oracle function whereas a deterministic classical computer would require 2−1 + 1 times evaluations.”
From QASMBench: A Low-Level Quantum Benchmark Suite for NISQ Evaluation and Simulation (2023) · cites this paper as [33]
BV algorithm is an extension to the Deutsch-Josza algorithm.
“The Bernstein-Vazirani algorithm [13] is an extension to the Deutsch-Josza algorithm [33].”
From QASMBench: A Low-Level Quantum Benchmark Suite for NISQ Evaluation and Simulation (2023) · cites this paper as [33]
Any physically allowed super-operator from k to l qubits can be described as a combination of adding k+l blank qubits, applying a unitary transformation on the 2k+l qubits, and then tracing out 2k qubits.
“A lemma by Choi[16], and Hellwig and Kraus[45] asserts that any physically allowed super-operator from k to l qubits can be described as a combination of the above three operations: add k + l blank qubits, apply a unitary transformation on the 2 k + l qubits and then trace out 2 k qubits.”
From Fault-Tolerant Quantum Computation with Constant Error Rate (2008) · cites this paper as [45]
Any super-operator that is trace-preserving and completely positive takes density matrices to density matrices.
“It turns out that any super operator which satisfies these conditions indeed take density matrices to density matrices[45].”
From Fault-Tolerant Quantum Computation with Constant Error Rate (2008) · cites this paper as [45]
A quantum computer can in principle exploit coherent quantum interference and entanglement to perform computations such as factoring large numbers or searching an unsorted database more rapidly than classical computers.
“In principle, it can exploit coherent quantum interference and entanglement to perform computations, such as factoring large numbers or searching an unsorted database, more rapidly than classical computers 1,2,6-8 .”
From Experimental realization of a quantum algorithm (1998) · cites this paper as [6]
They implemented the simplest possible version of the Deutsch-Jozsa quantum algorithm, which determines whether an unknown function is constant or balanced.
“We implemented the simplest possible version of the Deutsch-Jozsa (D-J) quantum algorithm 6 , which determines whether an unknown function is constant or balanced.”
From Experimental realization of a quantum algorithm (1998) · cites this paper as [6]
In 1996, Lloyd provided a concrete method for using quantum computers to efficiently simulate the dynamics of other quantum systems.
“In 1996, Feynman's vision was manifested in a theoretical proposal by Lloyd 37 , providing a concrete method for using quantum computers to efficiently simulate the dynamics of other quantum systems.”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [37]
With respect to a desired accuracy and duration of time evolution, the number of quantum gates grows polynomially in system size, time, and inverse precision.
“with respect to a desired accuracy and duration of the time evolution, the number of quantum gates (roughly, computation time) grows polynomially in system size, time, and inverse-precision.”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [37]
The wave function can be efficiently evolved in time for many physically realistic Hamiltonians.
“It is important that the wave function can be efficiently evolved in time for many 'physically realistic' Hamiltonians 37 .”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [37]
The ability to manipulate a discretization of the wave function directly opened a floodgate of new results in quantum algorithms for quantum chemistry.
“the ability to manipulate a discretization of the wave function directly opened a floodgate of new results in quantum algorithms for quantum chemistry 37,40,41,75,233 .”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [37]
Lloyd's analysis assumes that the Hamiltonian describes only local interactions.
“The structure assumed in Lloyd's analysis is that the Hamiltonian describes only local interactions .”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [37]
Lloyd's work gave a rigorous upper bound on the computational time for quantum simulation.
“the work of Lloyd gave a rigorous upper bound on the computational time for quantum simulation.”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [37]
Lloyd's result applies to gate-based or digital quantum simulation, which is distinct from analog quantum simulation.
“We emphasize that Lloyd's result applies to a particular approach to quantum simulation, known as gate-based or digital quantum simulation . This approach is distinct from an analog quantum simulation , for which there have been several recent ground-breaking experiments 245-249 .”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [37]
Independently of Lloyd's quantum simulation algorithm, Zalka introduced a quantum algorithm for simulation of single- and many-body quantum systems.
“Independently of Lloyd's quantum simulation algorithm 37 , Zalka 273 introduced a quantum algorithm for simulation of single- and many-body quantum systems.”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [37]
The best possible classical algorithm for the Deutsch-Jozsa problem uses at least 2^{n-1}+1 queries in the worst case.
“While the best possible classical algorithm to solve this problem uses at least 2 n -1 +1 queries in the worst case, the Deutsch-Jozsa algorithm takes advantage of quantum superposition and interference to determine whether f is constant or balanced with only one query.”
From Demonstration of Blind Quantum Computing (2012) · cites this paper as [2]
The Deutsch-Jozsa algorithm determines whether f is constant or balanced with only one query.
“the Deutsch-Jozsa algorithm takes advantage of quantum superposition and interference to determine whether f is constant or balanced with only one query.”
From Demonstration of Blind Quantum Computing (2012) · cites this paper as [2]
Cites
Quantum theory, the Church–Turing principle and the universal quantum computer
Deutsch, D. (1985) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1985.0070 · Cited by 4,597 · see citing works
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
Bennett, C. H., Brassard, G., Crépeau, C., Jozsa, R., Peres, A., & Wootters, W. K. (1993) · Physical Review Letters · doi:10.1103/physrevlett.70.1895 · Cited by 13,703 · see citing works
Self-citationA fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830 · see citing works
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713 · see citing works
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 · see citing works
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 · see citing works
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904 · see citing works
Charge-insensitive qubit design derived from the Cooper pair box
Koch, J., Yu, T. M., Gambetta, J., Houck, A. A., Schuster, D. I., Majer, J., Blais, A., Devoret, M. H., Girvin, S. M., & Schoelkopf, R. J. (2007) · Physical Review A · doi:10.1103/physreva.76.042319 · Cited by 3,351 · see citing works
Lloyd, S. (1996) · Science · doi:10.1126/science.273.5278.1073 · Cited by 3,088 · see citing works
Demonstration of a Fundamental Quantum Logic Gate
Monroe, C., Meekhof, D. M., King, B. E., Itano, W. M., & Wineland, D. J. (1995) · Physical Review Letters · doi:10.1103/physrevlett.75.4714 · Cited by 1,586 · see citing works
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546 · see citing works
Bulk Spin-Resonance Quantum Computation
Gershenfeld, N. A., & Chuang, I. L. (1997) · Science · doi:10.1126/science.275.5298.350 · Cited by 1,528 · see citing works
Quantum Chemistry in the Age of Quantum Computing
Cao, Y., Romero, J., Olson, J. P., Degroote, M., Johnson, P. D., Kieferová, M., Kivlichan, I. D., Menke, T., Peropadre, B., Sawaya, N. P. D., et al. (2019) · Chemical Reviews · doi:10.1021/acs.chemrev.8b00803 · Cited by 1,560 · see citing works
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470 · see citing works
Quantum computation and Shor's factoring algorithm
Ekert, A., & Jozsa, R. (1996) · Reviews of Modern Physics · doi:10.1103/revmodphys.68.733 · Cited by 1,354 · see citing works
Self-citationTrapped-ion quantum computing: Progress and challenges
Bruzewicz, C. D., Chiaverini, J., McConnell, R., & Sage, J. M. (2019) · Applied Physics Reviews · doi:10.1063/1.5088164 · Cited by 1,483 · see citing works
Bernstein, E., & Vazirani, U. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167097 · Cited by 1,284 · see citing works
Multiple-particle interference and quantum error correction
(1996) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1996.0136 · Cited by 1,284 · see citing works
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 · see citing works
Quantum computers and dissipation
(1996) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1996.0029 · Cited by 899 · see citing works
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 · see citing works
Self-citationExponential algorithmic speedup by a quantum walk
Childs, A. M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., & Spielman, D. A. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780552 · Cited by 825 · see citing works
Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
Abrams, D. S., & Lloyd, S. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.2586 · Cited by 745 · see citing works
Quantum lower bounds by polynomials
Beals, R., Buhrman, H., Cleve, R., Mosca, M., & de Wolf, R. (2001) · Journal of the ACM · doi:10.1145/502090.502097 · Cited by 639 · see citing works
Orchestrated reduction of quantum coherence in brain microtubules: a model for consciousness
Hameroff, S., & Penrose, R. (1996) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(96)80476-9 · Cited by 641 · see citing works
Fault-tolerant quantum computation with constant error
Aharonov, D., & Ben-Or, M. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258579 · Cited by 631 · see citing works
Experimental realization of a quantum algorithm
Chuang, I. L., Vandersypen, L. M. K., Zhou, X., Leung, D. W., & Lloyd, S. (1998) · Nature · doi:10.1038/30181 · Cited by 604 · see citing works
Maintaining coherence in quantum computers
Unruh, W. G. (1995) · Physical Review A · doi:10.1103/physreva.51.992 · Cited by 594 · see citing works
From quantum cellular automata to quantum lattice gases
Meyer, D. A. (1996) · Journal of Statistical Physics · doi:10.1007/bf02199356 · Cited by 556 · see citing works
Demonstration of Blind Quantum Computing
Barz, S., Kashefi, E., Broadbent, A., Fitzsimons, J. F., Zeilinger, A., & Walther, P. (2012) · Science · doi:10.1126/science.1214707 · Cited by 475 · see citing works
Fast universal quantum gate above the fault-tolerance threshold in silicon
Noiri, A., Takeda, K., Nakajima, T., Kobayashi, T., Sammak, A., Scappucci, G., & Tarucha, S. (2022) · Nature · doi:10.1038/s41586-021-04182-y · Cited by 471 · see citing works
Quantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344 · see citing works
Boson sampling for molecular vibronic spectra
Huh, J., Guerreschi, G. G., Peropadre, B., McClean, J. R., & Aspuru-Guzik, A. (2015) · Nature Photonics · doi:10.1038/nphoton.2015.153 · Cited by 341 · see citing works
Efficient networks for quantum factoring
Beckman, D., Chari, A. N., Devabhaktuni, S., & Preskill, J. (1996) · Physical Review A · doi:10.1103/physreva.54.1034 · Cited by 268 · see citing works
Quantum Computation and Lattice Problems
Regev, O. (2004) · SIAM Journal on Computing · doi:10.1137/s0097539703440678 · Cited by 188 · see citing works
Danos, V., Kashefi, E., & Panangaden, P. (2007) · Journal of the ACM · doi:10.1145/1219092.1219096 · Cited by 195 · see citing works
Coherent quantum transport in photonic lattices
Perez-Leija, A., Keil, R., Kay, A., Moya-Cessa, H., Nolte, S., Kwek, L.-C., Rodríguez-Lara, B. M., Szameit, A., & Christodoulides, D. N. (2013) · Physical Review A · doi:10.1103/physreva.87.012309 · Cited by 182 · see citing works
Quantum simulation of the wavefunction to probe frustrated Heisenberg spin systems
Ma, X.-S., Dakic, B., Naylor, W., Zeilinger, A., & Walther, P. (2011) · Nature Physics · doi:10.1038/nphys1919 · Cited by 179 · see citing works
QASMBench: A Low-Level Quantum Benchmark Suite for NISQ Evaluation and Simulation
Li, A., Stein, S., Krishnamoorthy, S., & Ang, J. (2023) · ACM Transactions on Quantum Computing · doi:10.1145/3550488 · Cited by 183 · see citing works
Jones, J. A. (2001) · Progress in Nuclear Magnetic Resonance Spectroscopy · doi:10.1016/s0079-6565(00)00033-9 · Cited by 177 · see citing works
Material platforms for integrated quantum photonics
Bogdanov, S., Shalaginov, M. Y., Boltasseva, A., & Shalaev, V. M. (2017) · Optical Materials Express · doi:10.1364/ome.7.000111 · Cited by 176 · see citing works
Quantum Optimization and Quantum Learning: A Survey
Li, Y., Tian, M., Liu, G., Peng, C., & Jiao, L. (2020) · IEEE Access · doi:10.1109/access.2020.2970105 · Cited by 177 · see citing works
Quantum Search Algorithms for Wireless Communications
Botsinis, P., Alanis, D., Babar, Z., Nguyen, H. V., Chandra, D., Ng, S. X., & Hanzo, L. (2019) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2018.2882385 · Cited by 149 · see citing works
Quantum resistant public key cryptography: a survey
Perlner, R. A., & Cooper, D. A. (2009) · Proceedings of the 8th Symposium on Identity and Trust on the Internet · doi:10.1145/1527017.1527028 · Cited by 137 · see citing works
Experimental realization of a quantum quincunx by use of linear optical elements
Do, B., Stohler, M. L., Balasubramanian, S., Elliott, D. S., Eash, C., Fischbach, E., Fischbach, M. A., Mills, A., & Zwickl, B. (2005) · Journal of the Optical Society of America B · doi:10.1364/josab.22.000499 · Cited by 128 · see citing works
Experimental Realization of Deutsch’s Algorithm in a One-Way Quantum Computer
Tame, M. S., Prevedel, R., Paternostro, M., Böhi, P., Kim, M. S., & Zeilinger, A. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.140501 · Cited by 124 · see citing works
Localization and its consequences for quantum walk algorithms and quantum communication
Keating, J. P., Linden, N., Matthews, J. C. F., & Winter, A. (2007) · Physical Review A · doi:10.1103/physreva.76.012315 · Cited by 123 · see citing works
Calculating the thermal rate constant with exponential speedup on a quantum computer
Lidar, D. A., & Wang, H. (1999) · Physical Review E · doi:10.1103/physreve.59.2429 · Cited by 115 · see citing works
Experimental realization of quantum algorithm for solving linear systems of equations
Pan, J., Cao, Y., Yao, X., Li, Z., Ju, C., Chen, H., Peng, X., Kais, S., & Du, J. (2014) · Physical Review A · doi:10.1103/physreva.89.022313 · Cited by 110 · see citing works
Early Fault-Tolerant Quantum Computing
Katabarwa, A., Gratsea, K., Caesura, A., & Johnson, P. D. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.020101 · Cited by 103 · see citing works
“It then it took about a decade before it was discovered that quantum phenomena, such as superposition and entanglement, could be leveraged to provide an exponential advantage in performing tasks unrelated to quantum mechanics [2].”
BackgroundBiology and medicine in the landscape of quantum advantages
Cordier, B. A., Sawaya, N. P. D., Guerreschi, G. G., & McWeeney, S. K. (2022) · Journal of The Royal Society Interface · doi:10.1098/rsif.2022.0541 · Cited by 87 · see citing works
Botsinis, P., Ng, S. X., & Hanzo, L. (2013) · IEEE Access · doi:10.1109/access.2013.2259536 · Cited by 64 · see citing works
Quantum theory and determinism
Vaidman, L. (2014) · Quantum Studies: Mathematics and Foundations · doi:10.1007/s40509-014-0008-4 · Cited by 65 · see citing works
Arithmetic on a distributed-memory quantum multicomputer
Meter, R. V., Munro, W. J., Nemoto, K., & Itoh, K. M. (2008) · ACM Journal on Emerging Technologies in Computing Systems · doi:10.1145/1324177.1324179 · Cited by 65 · see citing works
Quantum-Assisted Routing Optimization for Self-Organizing Networks
ALANIS, D., BOTSINIS, P., NG, S. X., & HANZO, L. (2014) · IEEE Access · doi:10.1109/access.2014.2327596 · Cited by 46 · see citing works
The Quantum Communication Complexity of Sampling
Ambainis, A., Schulman, L. J., Ta-Shma, A., Vazirani, U., & Wigderson, A. (2003) · SIAM Journal on Computing · doi:10.1137/s009753979935476 · Cited by 44 · see citing works
Quantum computing: the future of big data and artificial intelligence in spine
Mallow, G. M., Hornung, A., Barajas, J. N., Rudisill, S. S., An, H. S., & Samartzis, D. (2022) · Spine Surgery and Related Research · doi:10.22603/ssrr.2021-0251 · Cited by 36 · see citing works
Quantum medical images processing foundations and applications
Elaraby, A. (2022) · IET Quantum Communication · doi:10.1049/qtc2.12049 · Cited by 28 · see citing works
Gate-based quantum computing for protein design
Khatami, M. H., Mendes, U. C., Wiebe, N., & Kim, P. M. (2023) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1011033 · Cited by 26 · see citing works
Experimental realization of the Deutsch-Jozsa algorithm with a six-qubit cluster state
Vallone, G., Donati, G., Bruno, N., Chiuri, A., & Mataloni, P. (2010) · Physical Review A · doi:10.1103/physreva.81.050302 · Cited by 26 · see citing works
Why the Many-Worlds Interpretation?
Vaidman, L. (2022) · Quantum Reports · doi:10.3390/quantum4030018 · Cited by 22 · see citing works
Necessary and Sufficient Conditions for Quantum Computation
Lloyd, S. (1994) · Journal of Modern Optics · doi:10.1080/09500349414552341 · Cited by 19 · see citing works
Controllability and universal three-qubit quantum computation with trapped electron states
Pedersen, L. H., & Rangan, C. (2008) · Quantum Information Processing · doi:10.1007/s11128-007-0070-5 · Cited by 10 · see citing works
- Authors
- Deutsch, D., & Jozsa, R.
- Affiliations
- University of Oxford (GB)
- St Edmund Hall, Oxford OX1 4AR, U. K.
- Venue
- Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences
- Publisher
- The Royal Society
- Published
- 1992-12-08
- Volume
- 439
- Issue
- 1907
- Pages
- 553-558
- ISSN
- 0962-8444 (ISSN-L)
- 2053-9177
- OpenAlex
- W2050334794
- Cited by
- 2,700
- References
- 1
- Citations by year
- 2026: 55 · 2025: 147 · 2024: 135 · 2023: 175 · 2022: 139 · 2021: 149 · 2020: 126 · 2019: 109 · 2018: 94 · 2017: 81 · 2016: 76 · 2015: 101 · 2014: 89 · 2013: 70 · 2012: 81
- FWCI
- 21.73
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Proceedings of the Royal Society of London Series A Mathematical and Physical Sciences (publishedVersion)
- Bristol Research (University of Bristol) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- quantum computing, quantum algorithms, exponential speedup, classical computing, stochastic computing, problem classes, computational complexity
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
