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
Flagged first, then by citations
1 of the 38 references couldn’t be matched to a known paper.
Cited by
Sorted by citations
Items 201–300 of 1,000
Superiority of exact quantum automata for promise problems
Ambainis, A., & Yakaryılmaz, A. (2012) · Information Processing Letters · doi:10.1016/j.ipl.2012.01.001 · Cited by 58
The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
Gottesman, D., & Irani, S. (2009) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2009.22 · Cited by 59
Quantum Image Filtering in the Frequency Domain
Caraiman, S., & Manta, V. (2013) · Advances in Electrical and Computer Engineering · doi:10.4316/aece.2013.03013 · Cited by 57
Using Bernstein–Vazirani algorithm to attack block ciphers
Xie, H., & Yang, L. (2018) · Designs Codes and Cryptography · doi:10.1007/s10623-018-0510-5 · Cited by 59
Space-Bounded Quantum Complexity
Watrous, J. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1999.1655 · Cited by 59
Theory of one-tape linear-time Turing machines
Tadaki, K., Yamakami, T., & Lin, J. C. H. (2009) · Theoretical Computer Science · doi:10.1016/j.tcs.2009.08.031 · Cited by 63
The Symmetric Group Defies Strong Fourier Sampling
Moore, C., Russell, A. C., & Schulman, L. J. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2005.73 · Cited by 58
Квантовые вычисления: алгоритмы и исправление ошибок
Китаев, А. Ю., & Kitaev, A. Y. (1997) · Успехи математических наук · doi:10.4213/rm892 · Cited by 60
Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur?
Kobayashi, H., Matsumoto, K., & Yamakami, T. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-24587-2_21 · Cited by 73
Quantum Gravity Computers: On the Theory of Computation with Indefinite Causal Structure
Hardy, L. (2009) · The Western Ontario series in philosophy of science · doi:10.1007/978-1-4020-9107-0_21 · Cited by 57
An introduction to Boson-sampling
Gard, B., Motes, K., Olson, J., Rohde, P., & Dowling, J. (2015) · UTS ePRESS (University of Technology Sydney) · Cited by 56
Three problems in computer science
Valiant, L. G. (2003) · Journal of the ACM · doi:10.1145/602382.602410 · Cited by 56
Single quantum querying of a database
Terhal, B. M., & Smolin, J. A. (1998) · Physical Review A · doi:10.1103/physreva.58.1822 · Cited by 58
Quantum computational universality of hypergraph states with Pauli-X and Z basis measurements
Takeuchi, Y., Morimae, T., & Hayashi, M. (2019) · Scientific Reports · doi:10.1038/s41598-019-49968-3 · Cited by 58
Linear-algebraic λ-calculus: higher-order, encodings, and confluence.
Arrighi, P. J., & Gilles Dowek, B. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-70590-1_2 · Cited by 55
Hypercomputation and the Physical Church‐Turing Thesis
Cotogno, P. (2003) · The British Journal for the Philosophy of Science · doi:10.1093/bjps/54.2.181 · Cited by 54
Computing the NoncomputablePreprint
Kieu, T. D. (2002) · Cited by 59
Bonnetain, X., Leurent, G., Naya‐Plasencia, M., & Schrottenloher, A. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-92062-3_15 · Cited by 55
Regular Languages Accepted by Quantum Automata
Bertoni, A., & Carpentieri, M. (2001) · Information and Computation · doi:10.1006/inco.2000.2911 · Cited by 54
Non-Clifford Gates Are Required for Long-Term Memory
Nelson, J., Rajakumar, J., & Gullans, M. J. (2026) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.ccc.2026.38
Learning-with-errors problem is easy with quantum samples
Grilo, A. B., Kerenidis, I., & Zijlstra, T. (2019) · Physical Review A · doi:10.1103/physreva.99.032314 · Cited by 53
Ying, M., & Feng, Y. (2010) · Acta Informatica · doi:10.1007/s00236-010-0117-4 · Cited by 51
Tensor Network Quantum Simulator With Step-Dependent Parallelization
Lykov, D., Schutski, R., Galda, A., Vinokur, V. M., & Alexeev, Y. (2022) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce53715.2022.00081 · Cited by 52
Integrating Quantum Computing into Workflow Modeling and Execution
Weder, B., Breitenbücher, U., Leymann, F., & Wild, K. (2020) · IEEE/ACM International Conference on Utility and Cloud Computing (UCC) · doi:10.1109/ucc48980.2020.00046 · Cited by 61
Counting, fanout and the complexity of quantum ACC
Green, F., Homer, S., Moore, C., & Pollett, C. (2002) · Quantum Information and Computation · doi:10.26421/qic2.1-3 · Cited by 51
Robust Polynomials and Quantum Algorithms
Buhrman, H., Newman, I., Röhrig, H., & de Wolf, R. (2007) · Theory of Computing Systems · doi:10.1007/s00224-006-1313-z · Cited by 65
Benchmarking Neural Networks For Quantum Computations
Nguyen, N. H., Behrman, E., Moustafa, M. A., & Steck, J. E. (2019) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2019.2933394 · Cited by 54
Introduction to quantum algorithms
Shor, P. W. (2002) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/058/1922896 · Cited by 55
Determining the equivalence for one-way quantum finite automata
Li, L., & Qiu, D. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.03.021 · Cited by 50
Effect of unitary noise on Grover’s quantum search algorithm
Shapira, D., Mozes, S., & Biham, O. (2003) · Physical Review A · doi:10.1103/physreva.67.042301 · Cited by 50
Quantum Algorithms for Mixed Binary Optimization Applied to Transaction Settlement
Braine, L., Egger, D. J., Glick, J., & Woerner, S. (2021) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3063635 · Cited by 51
Mastriani, M. (2016) · Quantum Information Processing · doi:10.1007/s11128-016-1457-y · Cited by 51
Quantum Computational Complexity
Watrous, J. (2011) · Springer eBooks · doi:10.1007/978-1-4614-1800-9_147 · Cited by 55
Automata theory based on quantum logic: Reversibilities and pushdown automata
Qiu, D. (2007) · Theoretical Computer Science · doi:10.1016/j.tcs.2007.05.026 · Cited by 49
Quantum computation: Algorithms and Applications
Cho, C., Chen, C.-Y., Chen, K.-C., Huang, T., Hsu, M.-C., Cao, N., Zeng, B., Tan, S.-G., & Chang, C. (2021) · Chinese Journal of Physics · doi:10.1016/j.cjph.2021.05.001 · Cited by 54
Detecting Code Alteration by Creating a Temporary Memory Bottleneck
Gardner, R. W., Garera, S., & Rubin, A. D. (2009) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2009.2033231 · Cited by 47
Misuse Attacks on Post-quantum Cryptosystems
Băetu, C., Durak, F. B., Huguenin-Dumittan, L., Talayhan, A., & Serge Vaudenay, B. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-17656-3_26 · Cited by 47
On the structure of Clifford quantum cellular automata
Schlingemann, D.-M., Vogts, H., & Werner, R. F. (2008) · Journal of Mathematical Physics · doi:10.1063/1.3005565 · Cited by 46
On the Class of Languages Recognizable by 1-Way Quantum Finite Automata
Ambainis, A., Ķikusts, A., & Valdats, M. (2007) · Springer eBooks · doi:10.1007/3-540-44693-1_7 · Cited by 46
Computing Spin NetworksPreprint
Marzuoli, A., & Rasetti, M. (2004) · Cited by 49
An introduction to quantum annealing
de Falco, D., & Tamascelli, D. (2011) · RAIRO - Theoretical Informatics and Applications · doi:10.1051/ita/2011013 · Cited by 52
Reliability Modeling of NISQ- Era Quantum Computers
Liu, J., & Zhou, H. (2020) · IEEE International Symposium on Workload Characterization · doi:10.1109/iiswc50251.2020.00018 · Cited by 47
Full-Stack, Real-System Quantum Computer Studies: Architectural Comparisons and Design InsightsPreprint
Murali, P., Linke, N. M., Martonosi, M., Javadi-Abhari, A., Nguyen, N. H., & Alderete, C. H. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1905.11349 · Cited by 45
A fast quantum mechanical algorithm for database searchPreprint
Grover, L. K. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9605043 · Cited by 132
A Tensor Network based Decision Diagram for Representation of Quantum Circuits
Hong, X., Zhou, X., Li, S., Feng, Y., & Ying, M. (2022) · ACM Transactions on Design Automation of Electronic Systems · doi:10.1145/3514355 · Cited by 54
Application of Combinatorial Testing to Quantum Programs
Wang, X., Arcaini, P., Yue, T., & Ali, S. (2021) · IEEE International Conference on Software Quality, Reliability and Security (QRS) · doi:10.1109/qrs54544.2021.00029 · Cited by 44
Monoidal computer I: Basic computability by string diagrams
Pavlović, D. (2013) · Information and Computation · doi:10.1016/j.ic.2013.03.007 · Cited by 44
BosonSampling is robust against small errors in the network matrix
Arkhipov, A. (2015) · Physical Review A · doi:10.1103/physreva.92.062326 · Cited by 49
A review of procedures to evolve quantum algorithms
Gepp, A., & Stocks, P. (2009) · Genetic Programming and Evolvable Machines · doi:10.1007/s10710-009-9080-7 · Cited by 42
Quantum Speedup for Aeroscience and Engineering
Givi, P., Daley, A. J., Mavriplis, D. J., & Malik, M. R. (2020) · AIAA Journal · doi:10.2514/1.j059183 · Cited by 46
Towards quantum template matching
Curtis, D., & MEYER, D. A. (2004) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.506669 · Cited by 43
An Automata-Based Framework for Verification and Bug Hunting in Quantum Circuits
Chen, Y., Chung, K.-M., Lengál, O., Lin, J.-A., Tsai, W.-L., & Yen, D.-D. (2023) · Proceedings of the ACM on Programming Languages · doi:10.1145/3591270 · Cited by 62
Creating Very True Quantum Algorithms for Quantum Energy Based Computing
Nagata, K., Nakamura, T., Geurdes, H. J. F., Batle, J. A. I., Abdalla, S., Farouk, A., & Diep, D. N. (2017) · International Journal of Theoretical Physics · doi:10.1007/s10773-017-3630-1 · Cited by 42
Quantum-Enhanced Grid of the Future: A Primer
Eskandarpour, R., Ghosh, K., Khodaei, A., Paaso, E. A., & Zhang, L. (2020) · IEEE Access · doi:10.1109/access.2020.3031595 · Cited by 43
On Computational Power of Quantum Branching Programs
Ablayev, F. M., Gainutdinova, A., & Karpiński, M. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44669-9_8 · Cited by 42
NMR quantum information processing and entanglement
Laflamme, R., Cory, D. G., Negrevergne, C., & Viola, L. (2002) · Quantum Information and Computation · doi:10.26421/qic2.2-5 · Cited by 52
Mutation-based test generation for quantum programs with multi-objective search
Wang, X., Yu, T., Arcaini, P., Yue, T., & Ali, S. (2022) · Genetic and Evolutionary Computation Conference (GECCO) · doi:10.1145/3512290.3528869 · Cited by 41
Ethics of Quantum Computing: an Outline
Possati, L. M. (2023) · Philosophy & Technology · doi:10.1007/s13347-023-00651-6 · Cited by 51
Post-quantum distributed ledger technology: a systematic survey
Parida, N. K., Jatoth, C., Reddy, V. D., Hussain, M. M., & Faizi, J. (2023) · Scientific Reports · doi:10.1038/s41598-023-47331-1 · Cited by 52
Quantum-Merlin-Arthur–complete problems for stoquastic Hamiltonians and Markov matrices
Jordan, S. P., Gosset, D., & Love, P. J. (2010) · Physical Review A · doi:10.1103/physreva.81.032331 · Cited by 50
Search by Quantum Walks on Two-Dimensional Grid without Amplitude Amplification
Ambainis, A., Bačkurs, A., Nahimovs, N., Ozols, R., & Rivosh, A. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-35656-8_7 · Cited by 41
Is your quantum program bug-free?
Miranskyy, A. V., Zhang, L., & Doliskani, J. (2020) · IEEE/ACM International Conference on Software Engineering: New Ideas and Emerging Results (ICSE-NIER) · doi:10.1145/3377816.3381731 · Cited by 59
Towards the quantum-enabled technologies for development of drugs or delivery systems
Hassanzadeh, P. (2020) · Journal of Controlled Release · doi:10.1016/j.jconrel.2020.04.050 · Cited by 42
A better lower bound for quantum algorithms searching an ordered list
Ambainis, A. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sffcs.1999.814606 · Cited by 49
Analogies and differences between quantum and stochastic automata
Bertoni, A., & Carpentieri, M. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00154-7 · Cited by 43
Quantum branching programs and space-bounded nonuniform quantum complexity
Sauerhoff, M., & Sieling, D. (2005) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.12.031 · Cited by 41
Polynomial simulations of decohered quantum computers
Aharonov, D., & Ben-Or, M. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548463 · Cited by 41
Unambiguous discrimination among oracle operators
Chefles, A., Kitagawa, A., Takeoka, M., Sasaki, M., & Twamley, J. (2007) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8113/40/33/016 · Cited by 40
Scalable NMR Quantum ComputationPreprint
Schulman, L. J., & Vazirani, U. V. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9804060 · Cited by 46
Self-citationLimitations on continuous variable quantum algorithms with Fourier transforms
Adcock, M., Høyer, P., & Sanders, B. C. (2009) · New Journal of Physics · doi:10.1088/1367-2630/11/10/103035 · Cited by 38
Quantum computing and quadratically signed weight enumerators
Knill, E. H., & Laflamme, R. (2001) · Information Processing Letters · doi:10.1016/s0020-0190(00)00222-2 · Cited by 43
Danos, V., Kashefi, E., Panangaden, P., & Perdrix, S. (2009) · Cambridge University Press eBooks · doi:10.1017/cbo9781139193313.008 · Cited by 37
Patel, T., Potharaju, A., Li, B., Roy, R. B., & Tiwari, D. (2020) · SC20: International Conference for High Performance Computing, Networking, Storage and Analysis · doi:10.1109/sc41405.2020.00050 · Cited by 37
Stabilizing multiple topological fermions on a quantum computer
Koh, J. M., Tai, T., Phee, Y. H., Ng, W. E., & Lee, C. H. (2022) · npj Quantum Information · doi:10.1038/s41534-022-00527-1 · Cited by 40
Quantum implicit computational complexity
Lago, U. D., Masini, A., & Zorzi, M. (2009) · Theoretical Computer Science · doi:10.1016/j.tcs.2009.07.045 · Cited by 36
Ambainis, A., Špalek, R., & de Wolf, R. (2007) · Algorithmica · doi:10.1007/s00453-007-9022-9 · Cited by 44
Counting by quantum eigenvalue estimation
Mosca, M. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00217-6 · Cited by 38
Quantum games and quantum algorithms
Meyer, D. (2002) · Contemporary mathematics - American Mathematical Society · doi:10.1090/conm/305/05221 · Cited by 40
New quantum algorithm for studying NP-complete problemsPreprint
Ohya, M., & Volovich, I. V. (2003) · Cited by 38
Verifiable Quantum Advantage without Structure
Yamakawa, T., & Zhandry, M. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs54457.2022.00014 · Cited by 35
Learning DNF over the uniform distribution using a quantum example oracle
Bshouty, N. H., & Jackson, J. C. (1995) · Conference on Learning Theory · doi:10.1145/225298.225312 · Cited by 37
Fast-forwarding of Hamiltonians and exponentially precise measurements
Atia, Y., & Aharonov, D. (2017) · RePEc: Research Papers in Economics · Cited by 43
Quantum Identification of Boolean Oracles
Ambainis, A., Iwama, K., Kawachi, A., Masuda, H., Putra, R. H., & Yamashita, S. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24749-4_10 · Cited by 42
Lineal: A linear-algebraic Lambda-calculus
Arrighi, P. J., & Gilles Dowek, B. (2017) · Logical Methods in Computer Science · doi:10.23638/lmcs-13(1:8)2017 · Cited by 37
Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines
Grigoriev, D. Y. (1997) · Theoretical Computer Science · doi:10.1016/s0304-3975(96)00188-0 · Cited by 36
Limits on the ability of quantum states to convey classical messages
Nayak, A., & Salzman, J. (2006) · Journal of the ACM · doi:10.1145/1120582.1120587 · Cited by 36
A reformulation of Hilbert's tenth problem through quantum mechanics
Kieu, T. D. (2004) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.2003.1266 · Cited by 35
Local Transition Functions of Quantum Turing Machines
Ozawa, M., & Nishimura, H. (2000) · RAIRO - Theoretical Informatics and Applications · doi:10.1051/ita:2000123 · Cited by 38
Quantum Computing for High-School Students An Experience Report
Angara, P. P., Stege, U., & MacLean, A. (2020) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce49297.2020.00047 · Cited by 36
Implementing quantum genetic algorithms
Udrescu, M., Prodan, L., & Vlăduţiu, M. (2006) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/1128022.1128034 · Cited by 35
Modeling noisy quantum circuits using experimental characterization
Dahlhauser, M., & Humble, T. S. (2021) · Physical Review A · doi:10.1103/physreva.103.042603 · Cited by 39
Adaptive job and resource management for the growing quantum cloud
Ravi, G. S., Smith, K. N., Murali, P., & Chong, F. T. (2021) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce52317.2021.00047 · Cited by 46
Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno’s Theorem
Benatti, F., Krüger, T., Müller, M. P., Siegmund‐Schultze, R., & Szkoła, A. (2006) · Communications in Mathematical Physics · doi:10.1007/s00220-006-0027-z · Cited by 35
A Survey of Lower Bounds for Satisfiability and Related Problems
van Melkebeek, D. (2006) · now publishers, Inc. eBooks · doi:10.1561/9781601980854 · Cited by 36
Matchgate and space-bounded quantum computations are equivalent
Jozsa, R., Kraus, B., Miyake, A., Watrous, J., et al. (2010) · Cambridge University Engineering Department Publications Database · Cited by 35
Probabilities to Accept Languages by Quantum Finite Automata
Ambainis, A., Bonner, R., Freivalds, R., & Ķikusts, A. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48686-0_17 · Cited by 35
Quantum Fourier sampling simplified
Hales, L., & Hallgren, S. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301336 · Cited by 35
Quantum Computation Beyond the Circuit ModelPreprint
Jordan, S. P. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0809.2307 · Cited by 69
Characterizing Grover search algorithm on large-scale superconducting quantum computers
AbuGhanem, M. (2025) · Scientific Reports · doi:10.1038/s41598-024-80188-6 · Cited by 42
On Quantum Effects in a Theory of Biological Evolution
Martin-Delgado, M. A. (2012) · Scientific Reports · doi:10.1038/srep00302 · Cited by 35
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
