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 601–700 of 1,000
Superpolynomial Speedups Based on Almost Any Quantum Circuit
Hallgren, S., & Harrow, A. W. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-70575-8_64 · Cited by 10
Qiu, D. (2002) · International Journal of Theoretical Physics · doi:10.1023/a:1021031915281 · Cited by 10
Alternation in Quantum Programming: From Superposition of Data to Superposition of ProgramsPreprint
Ying, M., Yu, N., & Feng, Y. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1402.5172 · Cited by 21
Physics and the new computation
Vitanyi, P. M. B. (1995) · Lecture notes in computer science · doi:10.1007/3-540-60246-1_118 · Cited by 10
On quantum and classical space-bounded processes with algebraic transition amplitudes
Watrous, J. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sffcs.1999.814605 · Cited by 10
Quantum computation based on retarded and advanced propagation
Castagnoli, G. (1998) · Physica D Nonlinear Phenomena · doi:10.1016/s0167-2789(98)00044-x · Cited by 13
Quantum and Classical Query Complexities of Functions of Matrices
Montanaro, A., & Shao, C. (2024) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3618260.3649665 · Cited by 17
Quantum circuit oracles for Abstract Machine computations
Hines, P. (2009) · Theoretical Computer Science · doi:10.1016/j.tcs.2009.11.017 · Cited by 9
On the Completeness of Quantum Computation Models
Arrighi, P. J., & Gilles Dowek, B. (2010) · Cited by 9
Quantum Adversary (Upper) Bound
Kimmel, S. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31594-7_47 · Cited by 9
Model Reductions for Inference: Generality of Pairwise, Binary, and Planar Factor Graphs
Eaton, F., & Zoubin Ghahramani, A. (2013) · Neural Computation · doi:10.1162/neco_a_00441 · Cited by 9
Two new results about quantum exact learning
Arunachalam, S., Chakraborty, S., Lee, T., Paraashar, M., & de Wolf, R. (2021) · Quantum · doi:10.22331/q-2021-11-24-587 · Cited by 10
Probing and dressing magnetic impurities in a superconductor
Akkaravarawong, K., Väyrynen, J. I., Sau, J. D., Demler, E., Glazman, L. I., & Yao, N. Y. (2019) · Physical Review Research · doi:10.1103/physrevresearch.1.033091 · Cited by 9
Physics’ Evolution Toward Computing
Nakamura, T., & Nagata, K. (2020) · International Journal of Theoretical Physics · doi:10.1007/s10773-020-04661-4 · Cited by 9
Experiments with IBM Quantum Devices for Random Number Generation and String Matching
Savvas, I. Κ., Chernov, A. V., & Butakova, M. A. (2020) · Telecommunications Forum (TELFOR) · doi:10.1109/telfor51502.2020.9306624 · Cited by 9
Test Data-Driven Machine Learning Models for Reliable Quantum Circuit Output
Saravanan, V., & Saeed, S. M. (2021) · IEEE European Test Symposium (ETS) · doi:10.1109/ets50041.2021.9465405 · Cited by 9
A Theoretical Framework for Learning from Quantum Data
Heidari, M., Padakandla, A., & Wojciech Szpankowski, A. (2021) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit45174.2021.9517721 · Cited by 9
Evolution of Quantum Machine Learning and an Attempt of Its Application for SDN Intrusion Detection
Shinde, A. R., & Bendale, S. P. (2023) · Studies in computational intelligence · doi:10.1007/978-981-19-9530-9_22 · Cited by 9
Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding
Kawachi, A., & Yamakami, T. (2006) · Lecture notes in computer science · doi:10.1007/11787006_19 · Cited by 9
Is Grover’s Algorithm a Quantum Hidden Subgroup Algorithm?
Lomonaco, S. J., & Kauffman, L. H. (2007) · Quantum Information Processing · doi:10.1007/s11128-007-0066-1 · Cited by 13
Quantum entanglement as a new information processing resource
Gruska, J. (2003) · New Generation Computing · doi:10.1007/bf03037304 · Cited by 9
Construction of a universal quantum computer
Lagana, A. A., Lohe, M. A., & von Smekal, L. (2009) · Physical Review A · doi:10.1103/physreva.79.052322 · Cited by 9
Quantum Computation in Computational Geometry
Sadakane, K., SUGAWARA, N., & Tokuyama, T. (2002) · Interdisciplinary Information Sciences · doi:10.4036/iis.2002.129 · Cited by 9
Space-efficient simulation of quantum computers
Frank, M. P., Meyer-Baese, U. H., Chiorescu, I., Oniciuc, L., & van Engelen, R. A. (2009) · ACM Southeast Regional Conference (ACMSE) · doi:10.1145/1566445.1566554 · Cited by 9
Universality of quantum Turing machines with deterministic control
Mateus, P., Sernadas, A., & Souto, A. (2015) · Journal of Logic and Computation · doi:10.1093/logcom/exv008 · Cited by 9
Determinism and Computational Power of Real Measurement-Based Quantum Computation
Perdrix, S., & Sanselme, L. (2017) · Lecture notes in computer science · doi:10.1007/978-3-662-55751-8_31 · Cited by 9
Classical Lower Bounds from Quantum Upper Bounds
Ben-David, S., Bouland, A., Garg, A., & Kothari, R. (2018) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2018.00040 · Cited by 16
Unbounded-error quantum query complexity
Montanaro, A., Nishimura, H., & Raymond, R. (2011) · Theoretical Computer Science · doi:10.1016/j.tcs.2011.04.043 · Cited by 14
The computational power of matchgates and the XY interaction on arbitrary graphs
Brod, D. J., & Childs, A. M. (2014) · Quantum Information and Computation · doi:10.26421/qic14.11-12-1 · Cited by 12
Hines, P. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.07.015 · Cited by 9
Limits on entropic uncertainty relations
Ambainis, A. (2010) · Quantum Information and Computation · doi:10.26421/qic10.9-10-10 · Cited by 9
Das, R., & Kumar, A. (2004) · The Journal of Chemical Physics · doi:10.1063/1.1795674 · Cited by 9
Characterization of Universal Two-Qubit Hamiltonians
Childs, A. M., Leung, D., Mančinska, L., & Ozols, M. (2011) · Quantum Information and Computation · doi:10.26421/qic11.1-2 · Cited by 10
Solving Highly Constrained Search Problems with Quantum Computers
Hogg, T. (1998) · Cited by 9
Quantum simulation from the bottom up: the case of rebits
Koh, D. E., Niu, M. Y., & Yoder, T. J. (2018) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8121/aab9c4 · Cited by 8
Revythi, M., & Κούκιου, Γ. (2025) · Machine Learning and Knowledge Extraction · doi:10.3390/make7030075 · Cited by 11
Quantum algorithm to solve function inversion with time–space trade-off
Wu, W., & Zhang, H. (2017) · Quantum Information Processing · doi:10.1007/s11128-017-1622-y · Cited by 8
Symmetry-adapted encodings for qubit number reduction by point-group and other Boolean symmetries
Picozzi, D., & Tennyson, J. (2023) · Quantum Science and Technology · doi:10.1088/2058-9565/acd86c · Cited by 10
Cycle discrete-time quantum walks on a noisy quantum computer
Wadhia, V., Chancellor, N., & Kendon, V. M. (2024) · The European Physical Journal D · doi:10.1140/epjd/s10053-023-00795-2 · Cited by 9
Accelerating Quantum Circuit Simulation with Symbolic Execution and Loop Summarization
Chen, T.-F., Chen, Y., Jiang, J.-H. R., Jobranová, S., & Lengál, O. (2024) · doi:10.1145/3676536.3676711 · Cited by 8
Lower Bounds for Generalized Quantum Finite Automata
Mercer, M. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-88282-4_34 · Cited by 8
How Low can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?
Ambainis, A., & de Wolf, R. (2014) · Computational Complexity · doi:10.1007/s00037-014-0083-2 · Cited by 10
Quantum differential cryptanalysis
Денисенко, Д. (2021) · Journal of Computer Virology and Hacking Techniques · doi:10.1007/s11416-021-00395-x · Cited by 8
Quantum bounded query complexity
Buhrman, H., & van Dam, W. (2003) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.1999.766273 · Cited by 10
Quantum algorithms for testing and learning Boolean functions
Floess, D., Andersson, E., & Hillery, M. S. (2013) · Mathematical Structures in Computer Science · doi:10.1017/s0960129512000151 · Cited by 8
On the Complexity of Shor's Algorithm for Factorization
Cao, Z., & Liu, L. (2009) · International Symposium on Information Science and Engineering · doi:10.1109/isise.2009.86 · Cited by 8
Quantum algorithms using the curvelet transform
Liu, Y.-K. (2009) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1536414.1536469 · Cited by 8
An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation
Nishimura, H., & Yamakami, T. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-28629-5_65 · Cited by 8
Quantum algorithm for multivariate polynomial interpolation
Chen, J., Childs, A. M., & Hung, S.-H. (2018) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.2017.0480 · Cited by 9
Quantum states cannot be transmitted efficiently classically
Montanaro, A. (2019) · Quantum · doi:10.22331/q-2019-06-28-154 · Cited by 13
Cuffaro, M. E. (2018) · Philosophy of engineering and technology · doi:10.1007/978-3-319-93779-3_11 · Cited by 9
Analysis of Quantum Algorithms with Classical Systems Counterpart
Sihare, S. R., & Nath, V. V. (2017) · International Journal of Information Engineering and Electronic Business · doi:10.5815/ijieeb.2017.02.03 · Cited by 8
Generalization of the Bernstein–Vazirani algorithm beyond qubit systems
Nagata, K., Geurdes, H. J. F., Patro, S. K., Heidari, S., Farouk, A., & Nakamura, T. (2019) · Quantum Studies Mathematics and Foundations · doi:10.1007/s40509-019-00196-4 · Cited by 8
Effect on ion-trap quantum computers from the quantum nature of the driving field
Yang, B., & Yang, L. (2020) · Science China Information Sciences · doi:10.1007/s11432-019-2689-4 · Cited by 10
Quantum Computing for Computer Architects, Second Edition
Metodi, T. S., Faruque, A. I., & Chong, F. T. (2011) · Synthesis lectures on computer architecture · doi:10.2200/s00331ed1v01y201101cac013 · Cited by 11
Teaching Quantum Computing with the QuIDE Simulator
Rycerz, K., Patrzyk, J., Patrzyk, B., & Bubak, M. (2015) · Procedia Computer Science · doi:10.1016/j.procs.2015.05.374 · Cited by 8
Lower Bounds on the Size of Quantum Automata Accepting Unary Languages
Bertoni, A., Mereghetti, C., & Palano, B. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45208-9_8 · Cited by 8
Introduction to Recent Quantum Algorithms
Høyer, P. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44683-4_7 · Cited by 7
Entropy and algorithmic complexity in quantum information theory
Benatti, F. (2006) · Natural Computing · doi:10.1007/s11047-006-9017-5 · Cited by 8
Quantum and classical complexity classes: Separations, collapses, and closure properties
Spakowski, H., Thakur, M., & Tripathi, R. S. (2005) · Information and Computation · doi:10.1016/j.ic.2004.10.009 · Cited by 8
Quantum Finite Multitape Automata
Ambainis, A., Bonner, R., Freivalds, R., Golovkins, M., & Karpiński, M. (1999) · Lecture notes in computer science · doi:10.1007/3-540-47849-3_21 · Cited by 8
Unbounded-Error Quantum Query Complexity
Montanaro, A., Nishimura, H., & Raymond, R. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-92182-0_80 · Cited by 8
The Sturm-Liouville Eigenvalue Problem and NP-Complete Problems in the Quantum Setting with Queries
Papageorgiou, A., & Woźniakowski, H. (2006) · Quantum Information Processing · doi:10.1007/s11128-006-0043-0 · Cited by 7
A new quantum lower bound method,
Ambainis, A., Špalek, R., & de Wolf, R. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132604 · Cited by 11
The Quantum Measurement Problem and Physical reality: A Computation Theoretic Perspective
Srikanth, R. (2006) · Cited by 8
A new connection between quantum circuits, graphs and the Ising partition function
Geraci, J. (2008) · Quantum Information Processing · doi:10.1007/s11128-008-0084-7 · Cited by 9
Back to The Future: A Roadmap for Quantum Simulation From Vintage Quantum Chemistry
Love, P. J. (2014) · Advances in chemical physics · doi:10.1002/9781118742631.ch02 · Cited by 9
Abstract structure of unitary oracles for quantum algorithms
Zeng, W. J., & Vicary, J. (2014) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.172.19 · Cited by 8
Quantum stabilizer codes and beyondPreprint
Sarvepalli, P. K. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0810.2574 · Cited by 9
Phase Information in Quantum Oracle ComputingPreprint
Machta, J. L. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9805022 · Cited by 9
Quantum Circuits for Dynamic Runtime Assertions in Quantum ComputationPreprint
Liu, J., Byrd, G. T., & Zhou, H. (2019) · doi:10.36227/techrxiv.11319929 · Cited by 9
Quantum Key-Recovery Attacks on Permutation-Based Pseudorandom Functions
Sun, H.-W., Gao, F., Xu, R.-X., Li, D., Li, Z., & Zhang, K. (2025) · IEEE Internet of Things Journal · doi:10.1109/jiot.2025.3579024 · Cited by 7
Quantum algorithms for learning the algebraic normal form of quadratic Boolean functions
Hao, X., Zhang, F., Xia, S., & Zhou, Y. Z. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02778-3 · Cited by 7
Wang, H., Zhao, L., & Li, P. (2020) · International Journal of Approximate Reasoning · doi:10.1016/j.ijar.2020.11.002 · Cited by 7
Shukla, A., & Vedula, P. (2023) · Quantum Information Processing · doi:10.1007/s11128-023-03978-3 · Cited by 9
A quantum approach for digital signal processing
Shukla, A., & Vedula, P. (2023) · The European Physical Journal Plus · doi:10.1140/epjp/s13360-023-04730-7 · Cited by 7
Artificial intelligence and a universal quantum computer
Wichert, A. (2016) · AI Communications · doi:10.3233/aic-160699 · Cited by 7
Analysis of Classical and Quantum Computing Based on Grover and Shor Algorithm
Raj, G., Singh, D., & Madaan, A. (2017) · Smart innovation, systems and technologies · doi:10.1007/978-981-10-5547-8_43 · Cited by 7
Quantum algorithm for the root-finding problem
Nagata, K., & Nakamura, T. (2018) · Quantum Studies Mathematics and Foundations · doi:10.1007/s40509-018-0171-0 · Cited by 7
Monoidal Computer III: A Coalgebraic View of Computability and Complexity (Extended Abstract)
Pavlović, D., & Yahia, M. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-00389-0_10 · Cited by 7
Binary classification with classical instances and quantum labels
Caro, M. C. (2021) · Quantum Machine Intelligence · doi:10.1007/s42484-021-00043-z · Cited by 11
Generalization of Deutsch’s Algorithm
Nagata, K., & Nakamura, T. (2020) · International Journal of Theoretical Physics · doi:10.1007/s10773-020-04522-0 · Cited by 7
Channel Divergences and Complexity in Algebraic QFT
Hollands, S., & Ranallo, A. (2023) · Communications in Mathematical Physics · doi:10.1007/s00220-023-04855-x · Cited by 7
Impact of Unreliable Devices on Stability of Quantum Computations
Dasgupta, S., & Humble, T. S. (2024) · ACM Transactions on Quantum Computing · doi:10.1145/3682071 · Cited by 46
TOWARDS A NOVEL ENVIRONMENT FOR SIMULATION OF QUANTUM COMPUTING
Patrzyk, J., Patrzyk, B., Rycerz, K., & Bubak, M. (2015) · Computer Science · doi:10.7494/csci.2015.16.1.103 · Cited by 8
On Quantum Versions of the Yao Principle
de Graaf, M., & de Wolf, R. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45841-7_28 · Cited by 9
Halting of Quantum Turing Machines
Ozawa, M. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45833-6_6 · Cited by 7
DELETING A MARKED BASIS-STATE FROM AN EVEN SUPERPOSITION OF ALL BASIS-STATES WITH A SINGLE QUERY
Liu, Y., & LONG, G. L. (2009) · International Journal of Quantum Information · doi:10.1142/s0219749909005201 · Cited by 7
Simulated quantum computation of global minima
Zhu, J., Huang, Z., & Kais, S. (2009) · Molecular Physics · doi:10.1080/00268970903117126 · Cited by 6
Efficient Quantum Algorithms of Finding the Roots of a Polynomial Function
Nagata, K., Nakamura, T., Geurdes, H. J. F., Batle, J. A. I., Farouk, A., Diep, D. N., & Patro, S. K. (2018) · International Journal of Theoretical Physics · doi:10.1007/s10773-018-3776-5 · Cited by 7
Finding conjugate stabilizer subgroups in $\PSL$ and related groups
Denney, A., Moore, C., & Russell, A. C. (2010) · Quantum Information and Computation · doi:10.26421/qic10.3-4-8 · Cited by 7
Quantum Kolmogorov complexity and quantum key distribution
Miyadera, T., & Imai, H. (2009) · Physical Review A · doi:10.1103/physreva.79.012324 · Cited by 7
THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY
Rogers, C., & Vedral, V. (2008) · Modern Physics Letters B · doi:10.1142/s021798490801464x · Cited by 7
Chin, T.-J., Suter, D., Chng, S.-F., & Quach, J. Q. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-69525-5_29 · Cited by 7
Linking information reconciliation and privacy amplification
Cachin, C., & Maurer, U. M. (1995) · Lecture notes in computer science · doi:10.1007/bfb0053442 · Cited by 7
VERIFIER-BASED ALGORITHM FOR UNSORTED DATABASE SEARCH PROBLEM
Wu, X., & LONG, G. L. (2007) · International Journal of Quantum Information · doi:10.1142/s0219749907003067 · Cited by 7
On the simulation of quantum turing machines
Carpentieri, M. (2003) · Theoretical Computer Science · doi:10.1016/s0304-3975(03)00054-9 · Cited by 7
Quantum Algorithms Know in Advance 50% of the Solution They Will Find in the Future
Castagnoli, G. (2009) · International Journal of Theoretical Physics · doi:10.1007/s10773-009-0143-6 · Cited by 7
Some Issues in Quantum Information Theory
Duan, R., Ji, Z., Feng, Y., & Ying, M. (2006) · Journal of Computer Science and Technology · doi:10.1007/s11390-006-0776-3 · Cited by 7
Theory of One Tape Linear Time Turing Machines
Tadaki, K., Yamakami, T., & Lin, J. C. H. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24618-3_29 · Cited by 7
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
