The DOI matches its Crossref record; 37 of the 38 references it cites were found in a registry or an index.
Quantum complexity theory
Abstract
Abstract. In this paper we study quantum computation from a complexity theoretic viewpoint. Our rst result is the existence of an ecient universal quantum Turing machine in Deutsch’s model of a quantum Turing machine (QTM) [Proc. Roy. Soc. London Ser. A, 400 (1985), pp. 97{117]. This construction is substantially more complicated than the corresponding construction for classical Turing machines (TMs); in fact, even simple primitives such as looping, branching, and composition are not straightforward in the context of quantum Turing machines. We establish how these familiar primitives can be implemented and introduce some new, purely quantum mechanical primitives, such as changing the computational basis and carrying out an arbitrary unitary transformation of polynomially bounded dimension. We also consider the precision to which the transition amplitudes of a quantum Turing machine need to be specied. We prove that O(log T) bits of precision suce to support a T step computation. This justies the claim that the quantum Turing machine model should be regarded as a discrete model of computation and not an analog one. We give the rst formal evidence that quantum Turing machines violate the modern (complexity theoretic) formulation of the Church{Turing thesis. We show the existence of a problem, relative to an oracle, that can be solved in polynomial time on a quantum Turing machine, but requires superpolynomial time on a bounded-error probabilistic Turing machine, and thus not in the class BPP. The class BQP of languages that are eciently decidable (with small error-probability) on a quantum Turing machine satises BPP ⊆ BQP ⊆ P]P. Therefore, there is no possibility of giving a mathematical proof that quantum Turing machines are more powerful than classical probabilistic Turing machines (in the unrelativized setting) unless there is a major breakthrough in complexity theory.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
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?
In the citing paper
“Lemma 4.11 If M is a normal form QTM which halts on all inputs, then there is a normal form QTM M ′ that reverses the computation of M with slowdown by a factor of 5.”
From Strengths and Weaknesses of Quantum Computing (1997) · cites this paper as [4]
In the citing paper
“Lemma 4.6 Given any QTM M = (Σ , Q, δ ) and any set Σ ′ , there is a QTM M ′ = (Σ × Σ ′ , Q, δ ′ ) such that M ′ behaves exactly as M while leaving its second track unchanged.”
From Strengths and Weaknesses of Quantum Computing (1997) · cites this paper as [4]
In the citing paper
“Lemma 4.8 If M 1 and M 2 are well-behaved, normal form QTMs with the same alphabet, then there is a normal form QTM M which carries out the computation of M 1 followed by the computation of M 2 .”
From Strengths and Weaknesses of Quantum Computing (1997) · cites this paper as [4]
In the citing paper
“Theorem 4.4 If f is a function mapping strings to strings which can be computed in deterministic polynomial time and such that the length of f ( x ) depends only on the length of x , then there is a polynomial-time, stationary, normal form QTM which given input x , produces output x ; f ( x ) , and whose running time depends only on the length of x .”
From Strengths and Weaknesses of Quantum Computing (1997) · cites this paper as [4]
In the citing paper
“Lemma 4.7 Given any QTM M = (Σ 1 ×···× Σ k , Q, δ ) and permutation π : [1 , k ] → [1 , k ] , there is a QTM M ′ = (Σ π (1) ×···× Σ π ( k ) , Q, δ ′ ) such that the M ′ behaves exactly as M except that its tracks are permuted according to π .”
From Strengths and Weaknesses of Quantum Computing (1997) · cites this paper as [4]
In the citing paper
“If f is a one-to-one function from strings to strings that such that both f and f -1 can be computed in deterministic polynomial time, and such that the length of f ( x ) depends only on the length of x , then there is a polynomial-time, stationary, normal form QTM which given input x , produces output f ( x ) , and whose running time depends only on the length of x .”
From Strengths and Weaknesses of Quantum Computing (1997) · cites this paper as [4]
In the citing paper
“Lemma 4.9 Suppose that M is a well-behaved, normal form QTM. Then there is a normal form QTM M ′ such that on input x ; k with k > 0 , the machine M ′ runs M for k iterations on its first track.”
From Strengths and Weaknesses of Quantum Computing (1997) · cites this paper as [4]
Citations
Cites
A 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
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
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
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
Logical Reversibility of Computation
Bennett, C. H. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.176.0525 · Cited by 3,679
Rapid solution of problems by quantum computation
Deutsch, D., & Jozsa, R. (1992) · Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences · doi:10.1098/rspa.1992.0167 · Cited by 2,700
Good quantum error-correcting codes exist
Calderbank, A. R., & Shor, P. W. (1996) · Physical Review A · doi:10.1103/physreva.54.1098 · Cited by 2,516
Cohen-Tannoudji, C. N., & Laloë, F. (1977) · Cited by 1,886
Feynman, R. P. (1986) · Foundations of Physics · doi:10.1007/bf01886518 · Cited by 1,770
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
Self-citation
Cited by
Sorted by citations
A 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
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
Quantum supremacy using a programmable superconducting processor
Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., Biswas, R., Boixo, S., Brandao, F. G. S. L., Buell, D. A., et al. (2019) · Nature · doi:10.1038/s41586-019-1666-5 · Cited by 7,720
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
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
Measurement-based quantum computation on cluster states
Raussendorf, R., Browne, D. E., & Briegel, H. J. (2003) · Physical Review A · doi:10.1103/physreva.68.022312 · Cited by 1,655
Quantum computational chemistry
McArdle, S., Endo, S., Aspuru-Guzik, A., Benjamin, S. C., & Yuan, X. (2020) · Reviews of Modern Physics · doi:10.1103/revmodphys.92.015003 · Cited by 1,621
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
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
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
Self-citationQuantum computations: algorithms and error correction
Kitaev, A. Y. (1997) · Russian Mathematical Surveys · doi:10.1070/rm1997v052n06abeh002155 · Cited by 1,424
Steane, A. (1998) · Reports on Progress in Physics · doi:10.1088/0034-4885/61/2/002 · Cited by 1,391
Cleve, R., EKERT, A. K., Macchiavello, C., & Mosca, M. (1998) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.1998.0164 · Cited by 1,399
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
Quantum Chemistry in the Age of Quantum Computing
Cao, Y., Romero, J., Olson, J., Degroote, M., Johnson, P., Kieferová, M., Kivlichan, I., Menke, T., Peropadre, B., Sawaya, N., et al. (n.d.) · OPUS - Open Publications of UTS Scholars (University of Technology Sydney) · Cited by 1,265
Most Tensor Problems Are NP-Hard
Hillar, C. J., & Lim, L. (2013) · Journal of the ACM · doi:10.1145/2512329 · Cited by 1,194
Measurement-based quantum computation
Briegel, H. J., Browne, D. E., Dür, W., Raussendorf, R., & Van den Nest, M. (2009) · Nature Physics · doi:10.1038/nphys1157 · Cited by 1,090
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
Machine learning & artificial intelligence in the quantum domain: a review of recent progress
Dunjko, V., & Briegel, H. J. (2018) · Reports on Progress in Physics · doi:10.1088/1361-6633/aab406 · Cited by 1,241
Quantum random walks - an introductory overview
Kempe, J., & Einstein, A. (2003) · Cited by 1,035
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
Fault-tolerant quantum computation
Shor, P. W. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1996.548464 · Cited by 1,195
The computational complexity of linear optics
Aaronson, S., & Arkhipov, A. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993682 · Cited by 874
Multiple particle interference and quantum error correction
Steane, A. M. (1996) · Cited by 871
Exponential 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
Demonstration of a small programmable quantum computer with atomic qubits
Debnath, S., Linke, N. M., Figgatt, C., Landsman, K. A., Wright, K., & Monroe, C. (2016) · Nature · doi:10.1038/nature18648 · Cited by 777
Quantum Walk Algorithm for Element Distinctness
Ambainis, A. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447311 · Cited by 814
Knill, E., Laflamme, R., & Zurek, W. H. (1998) · Science · doi:10.1126/science.279.5349.342 · Cited by 663
Distance measures to compare real and ideal quantum processes
Gilchrist, A., Langford, N. K., & Nielsen, M. A. (2005) · Physical Review A · doi:10.1103/physreva.71.062310 · Cited by 548
A Survey on quantum computing technology
Gyongyosi, L., & Imre, S. (2019) · Computer Science Review · doi:10.1016/j.cosrev.2018.11.002 · Cited by 646
Yao, A. C.-C. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1993.366852 · Cited by 680
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
Information and computation: Classical and quantum aspects
Galindo, A., & Martin-Delgado, M. A. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.347 · Cited by 563
Benchmarking an 11-qubit quantum computer
Wright, K., Beck, K. M., Debnath, S., Amini, J., Nam, Y., Grzesiak, N., Chen, J.-S., Pisenti, N. C., Chmielewski, M., Collins, C., et al. (2019) · Nature Communications · doi:10.1038/s41467-019-13534-2 · Cited by 575
Experimental comparison of two quantum computing architectures
Linke, N. M., Maslov, D., Roetteler, M., Debnath, S., Figgatt, C., Landsman, K. A., Wright, K., & Monroe, C. (2017) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1618020114 · Cited by 508
Schlosshauer, M. (2019) · Physics Reports · doi:10.1016/j.physrep.2019.10.001 · Cited by 603
On the power of quantum computation
Simon, D. R. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365701 · Cited by 491
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 579
Random Oracles in a Quantum World
Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., & Zhandry, M. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-25385-0_3 · Cited by 507
From Quantum Cellular Automata To Quantum Lattice GasesPreprint
Meyer, D., Qca, F., David, Q., & Meyer, A. (1996) · Cited by 502
Quantum measurements and the Abelian Stabilizer ProblemPreprint
Kitaev, A. (1995) · arXiv (Cornell University) · Cited by 472
Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
Zhong, H.-S., Deng, Y.-H., Qin, J., Wang, H., Chen, M.-C., Peng, L.-C., Luo, Y.-H., Wu, D., Gong, S.-Q., Su, H., et al. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.180502 · Cited by 434
Quantum circuits with mixed states
Aharonov, D., Kitaev, A., & Nisan, N. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276708 · Cited by 487
Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers
Murali, P., Baker, J. M., Javadi-Abhari, A., Chong, F. T., & Martonosi, M. (2019) · Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/3297858.3304075 · Cited by 411
An introduction to quantum computing for non-physicists
Rieffel, E. G., & Polak, W. (2000) · ACM Computing Surveys · doi:10.1145/367701.367709 · Cited by 436
Quantum advantage with shallow circuits
Bravyi, S. B., Gosset, D., & König, R. (2018) · Science · doi:10.1126/science.aar3106 · Cited by 406
Local Random Quantum Circuits are Approximate Polynomial-Designs
Brandão, F. G. S. L., Harrow, A. W., & Horodecki, M. (2016) · Communications in Mathematical Physics · doi:10.1007/s00220-016-2706-8 · Cited by 404
Quantum machine learning: a classical perspective
Ciliberto, C., Herbster, M., Ialongo, A. D., Pontil, M., Rocchetto, A., Severini, S., & Wossnig, L. (2018) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2017.0551 · Cited by 518
Quantum vs. classical communication and computation
Buhrman, H., Cleve, R., & Wigderson, A. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276713 · Cited by 428
Polynomial-time quantum algorithm for the simulation of chemical dynamics
Kassal, I., Jordan, S. P., Love, P. J., Mohseni, M., & Aspuru-Guzik, A. (2008) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0808245105 · Cited by 385
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 358
On the power of quantum finite state automata
Kondacs, A., & Watrous, J. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646094 · Cited by 356
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
Resilient quantum computation: error models and thresholds
Knill, E., Laflamme, R., & Zurek, W. H. (1998) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1998.0166 · Cited by 346
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
Quantum computing, postselection, and probabilistic polynomial-time
Aaronson, S. (2005) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.2005.1546 · Cited by 312
Magniez, F., Nayak, A., Roland, J., & Santha, M. (2011) · SIAM Journal on Computing · doi:10.1137/090745854 · Cited by 294
On the complexity and verification of quantum random circuit sampling
Bouland, A., Fefferman, B., Nirkhe, C., & Vazirani, U. (2019) · Nature Physics · doi:10.1038/s41567-018-0318-2 · Cited by 287
Self-citationQuantum computation and quantum information
Nagy, M., & Akl, S. G. (2005) · International Journal of Parallel Emergent and Distributed Systems · doi:10.1080/17445760500355678 · Cited by 320
Simulating Large Quantum Circuits on a Small Quantum Computer
Peng, T., Harrow, A. W., Ozols, M., & Wu, X. (2020) · Physical Review Letters · doi:10.1103/physrevlett.125.150504 · Cited by 324
Undecidability of the spectral gap
Cubitt, T. S., Pérez-Garcı́a, D., & Wolf, M. M. (2015) · Nature · doi:10.1038/nature16059 · Cited by 279
An exact quantum polynomial-time algorithm for Simon's problem
Brassard, G., & Høyer, P. (2002) · Israel Symposium on Theory and Computing Systems (ISTCS) · doi:10.1109/istcs.1997.595153 · Cited by 255
A framework for fast quantum mechanical algorithms
Grover, L. K. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276712 · Cited by 236
Quantum Algorithm Implementations for Beginners
Jayakumar, A., Adedoyin, A. A., Ambrosiano, J. J., Anisimov, P. M., Casper, W., Chennupati, G., Coffrin, C., Djidjev, H. N., Gunter, D., Karra, S., et al. (2022) · ACM Transactions on Quantum Computing · doi:10.1145/3517340 · Cited by 362
Sophisticated Quantum Search Without Entanglement
Meyer, D. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.2014 · Cited by 242
BQP and the polynomial hierarchy
Aaronson, S. (2010) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1806689.1806711 · Cited by 257
Exponential separation of quantum and classical communication complexity
Raz, R. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301343 · Cited by 223
Quantum distinguisher between the 3-round Feistel cipher and the random permutation
Kuwakado, H., & Morii, M. (2010) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit.2010.5513654 · Cited by 221
Quantum discord and its allies: a review of recent progress
Bera, A., Das, T., Sadhukhan, D., Roy, S. S., Sen, A., & Sen, U. (2017) · Reports on Progress in Physics · doi:10.1088/1361-6633/aa872f · Cited by 229
1-way quantum finite automata: strengths, weaknesses and generalizations
Ambainis, A., & Freivalds, R. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1998.743469 · Cited by 220
Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
Kitaev, A., & Watrous, J. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335387 · Cited by 232
Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity
Watrous, J. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2000.1732 · Cited by 212
Quantum Walk Algorithm for Element Distinctness
Ambainis, A. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.54 · Cited by 226
Quantum algorithms: entanglement–enhanced information processing
EKERT, A. K., & Jozsa, R. (1998) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.1998.0248 · Cited by 230
A Resource Framework for Quantum Shannon Theory
Devetak, I., Harrow, A. W., & Winter, A. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2008.928980 · Cited by 216
The Path to Scalable Distributed Quantum Computing
Meter, R. V., & Devitt, S. J. (2016) · Computer · doi:10.1109/mc.2016.291 · Cited by 220
A Lambda Calculus for Quantum Computation
van Tonder, A. (2004) · SIAM Journal on Computing · doi:10.1137/s0097539703432165 · Cited by 206
Gupta, S., & Zia, R. K. P. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2001.1769 · Cited by 201
Danos, V., Kashefi, E., & Panangaden, P. (2007) · Journal of the ACM · doi:10.1145/1219092.1219096 · Cited by 195
A new universal and fault-tolerant quantum basis
Boykin, P. O., Mor, T., Pulver, M., Roychowdhury, V., & Vatan, F. (2000) · Information Processing Letters · doi:10.1016/s0020-0190(00)00084-3 · Cited by 194
Ullah, U., & García-Zapirain, B. (2024) · IEEE Access · doi:10.1109/access.2024.3353461 · Cited by 224
Quantum Speedup for Active Learning Agents
Paparo, G. D., Dunjko, V., Makmal, A., Martin-Delgado, M. A., & Briegel, H. J. (2014) · Physical Review X · doi:10.1103/physrevx.4.031002 · Cited by 192
Adiabatic Quantum Simulation of Quantum Chemistry
Babbush, R., Love, P. J., & Aspuru-Guzik, A. (2014) · Scientific Reports · doi:10.1038/srep06603 · Cited by 191
Maciejewski, F., Zimborás, Z., & Oszmaniec, M. (2020) · Repository of the Academy's Library (Library of the Hungarian Academy of Sciences) · Cited by 184
Quantum programming languages: survey and bibliography
Gay, S. J. (2006) · Mathematical Structures in Computer Science · doi:10.1017/s0960129506005378 · Cited by 173
Verification of Quantum Computation: An Overview of Existing Approaches
Gheorghiu, A., Kapourniotis, T., & Kashefi, E. (2018) · Theory of Computing Systems · doi:10.1007/s00224-018-9872-3 · Cited by 209
Emerging quantum computing algorithms for quantum chemistry
Motta, M., & Rice, J. E. (2021) · Wiley Interdisciplinary Reviews Computational Molecular Science · doi:10.1002/wcms.1580 · Cited by 201
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
Standard model physics and the digital quantum revolution: thoughts about the interface
Klco, N., Roggero, A., & A, M. J. S. (2022) · Reports on Progress in Physics · doi:10.1088/1361-6633/ac58a4 · Cited by 209
An improved quantum Fourier transform algorithm and applications
Hales, L., & Hallgren, S. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892139 · Cited by 165
Quantum Cryptanalysis of Hidden Linear Functions
Boneh, D., & Lipton, R. J. (1995) · Lecture Notes in Computer Science · doi:10.1007/3-540-44750-4_34 · Cited by 161
Circuit complexity in interacting QFTs and RG flows
Bhattacharyya, A., Shekar, A., & Sinha, A. (2018) · Journal of High Energy Physics · doi:10.1007/jhep10(2018)140 · Cited by 161
On one-dimensional quantum cellular automata
Watrous, J. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1995.492583 · Cited by 156
Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
Hallgren, S. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.510001 · Cited by 157
Deng, Y., Gu, Y.-C., Liu, H.-L., Gong, S.-Q., Su, H., Zhang, Z.-J., Tang, H., Jia, M.-H., Xu, J., Chen, M.-C., et al. (2023) · Physical Review Letters · doi:10.1103/physrevlett.131.150601 · Cited by 176
Guest Column: A Survey of Quantum Learning Theory
Arunachalam, S., & de Wolf, R. (2017) · ACM SIGACT News · doi:10.1145/3106700.3106710 · Cited by 152
Computational Complexity and Human Decision-Making
Bossaerts, P. L., & Murawski, C. (2017) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2017.09.005 · Cited by 162
Characterizations of 1-Way Quantum Finite Automata
Brodsky, A., & Pippenger, N. J. (2002) · SIAM Journal on Computing · doi:10.1137/s0097539799353443 · Cited by 151
Toward an architecture for quantum programming
Bettelli, S., Calarco, T., & Serafini, L. (2003) · The European Physical Journal D · doi:10.1140/epjd/e2003-00242-2 · Cited by 148
Metadata
- Authors
- Bernstein, E., & Vazirani, U.
- Venue
- Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93
- Publisher
- ACM Press
- Published
- 1993
- Pages
- 11-20
- OpenAlex
- W1993688167
- Cited by
- 1,284
- References
- 38
- Citations by year
- 2026: 22 · 2025: 54 · 2024: 47 · 2023: 71 · 2022: 51 · 2021: 74 · 2020: 68 · 2019: 50 · 2018: 34 · 2017: 37 · 2016: 39 · 2015: 26 · 2014: 35 · 2013: 33 · 2012: 36
- FWCI
- 16.24
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM Symposium on Theory of Computing (STOC) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- quantum Turing machines, Church-Turing thesis, BQP, BPP, oracle separation, quantum computing
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
