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 401–500 of 1,000
Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure
Zhan, B., Kimmel, S., & Hassidim, A. (2012) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2090236.2090258 · Cited by 23
Some formal tools for analyzing quantum automata
Bertoni, A., Mereghetti, C., & Palano, B. (2006) · Theoretical Computer Science · doi:10.1016/j.tcs.2006.01.042 · Cited by 23
Quantum Mechanical Model of Emotional Robot Behaviors
Lukac, M., & Perkowski, M. A. (2007) · IEEE International Symposium on Multiple-Valued Logic (ISMVL) · doi:10.1109/ismvl.2007.44 · Cited by 23
Measurement-Based and Universal Blind Quantum Computation
Broadbent, A., Fitzsimons, J. F., & Kashefi, E. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13678-8_2 · Cited by 23
Quantum computing and the chaotic amplifier
Ohya, M., & Volovich, I. V. (2003) · Journal of Optics B Quantum and Semiclassical Optics · doi:10.1088/1464-4266/5/6/015 · Cited by 23
A framework for structured quantum search
Hogg, T. (1998) · Physica D Nonlinear Phenomena · doi:10.1016/s0167-2789(98)00047-5 · Cited by 27
The Symmetric Group Defies Strong Fourier Sampling: Part IIPreprint
Moore, C., & Russell, A. C. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0501066 · Cited by 23
Quantum Computation with Topological Codes: from qubit to topological fault-tolerancePreprint
Fujii, K. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1504.01444 · Cited by 23
Rapid sampling through quantum computingPreprint
Grover, L. K. (1999) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9912001 · Cited by 23
Aaronson, S. (2016) · Springer eBooks · doi:10.1007/978-3-319-32162-2_1 · Cited by 40
Demonstration of essentiality of entanglement in a Deutsch-like quantum algorithm
Huang, H.-L., Goswami, A., Bao, W., & Panigrahi, P. K. (2018) · Science China Physics Mechanics and Astronomy · doi:10.1007/s11433-018-9175-2 · Cited by 25
Neuromorphic Computing is Turing-Complete
Date, P., Potok, T. E., Schuman, C. D., & Kay, B. (2022) · International Conference on Neuromorphic Systems (ICONS) · doi:10.1145/3546790.3546806 · Cited by 30
Quantum computing: beyond the limits of conventional computation†
Nagy, M., & Akl, S. G. (2007) · International Journal of Parallel Emergent and Distributed Systems · doi:10.1080/13547500600899209 · Cited by 22
The Quantum Black-Box Complexity of Majority
Available, N. A. N., Available, N. A. N., & van Melkebeek, D. (2002) · Algorithmica · doi:10.1007/s00453-002-0981-6 · Cited by 23
Mendes, R. V. (2005) · Quantum Information Processing · doi:10.1007/s11128-005-3192-7 · Cited by 22
Brain Computation: A Computer Science Perspective
Maass, W., Papadimitriou, C. H., Vempala, S., & Legenstein, R. A. (2019) · Lecture notes in computer science · doi:10.1007/978-3-319-91908-9_11 · Cited by 21
Tripartite Entanglement Measures of Generalized GHZ State in Uniform Acceleration*
Dong, Q., Sanchez, M. A. M., Sun, G.-H., Toutounji, M. M., & Dong, S. (2019) · Chinese Physics Letters · doi:10.1088/0256-307x/36/10/100301 · Cited by 22
Quantum Nondemolition Circuit for Testing Bipartite Complementarity
de Melo, F., Walborn, S. P., Bergou, J. A., & Davidovich, L. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.250501 · Cited by 22
van Dam, W. (1996) · Cited by 22
Gruska, J. (2001) · Springer eBooks · doi:10.1007/978-3-642-56478-9_27 · Cited by 22
GENERALIZED QUANTUM TURING MACHINE AND ITS APPLICATION TO THE SAT CHAOS ALGORITHM
Iriyama, S., Ohya, M., & Volovich, I. V. (2006) · doi:10.1142/9789812774491_0017 · Cited by 23
Zeno machines and hypercomputation
Potgieter, P. H. (2006) · Theoretical Computer Science · doi:10.1016/j.tcs.2005.11.040 · Cited by 25
Assessing Solution Quality of 3SAT on a Quantum Annealing Platform
Gabor, T., Zielinski, S., Feld, S., Roch, C., Seidel, C., Neukart, F., Galter, I., Mauerer, W., & Linnhoff-Popien, C. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-14082-3_3 · Cited by 21
Quantum Computation and Information
Vazirani, U. V. (1998) · Lecture notes in computer science · doi:10.1007/978-3-540-49382-2_34 · Cited by 21
Self-citationTrace monoids with idempotent generators and measure-only quantum automata
Bertoni, A., Mereghetti, C., & Palano, B. (2009) · Natural Computing · doi:10.1007/s11047-009-9154-8 · Cited by 21
Nested quantum annealing correction at finite temperature: p -spin models
Matsuura, S., Nishimori, H., Vinci, W., & Lidar, D. A. (2019) · Physical Review A · doi:10.1103/physreva.99.062307 · Cited by 21
Tetrapartite entanglement measures of GHZ state with uniform acceleration
Dong, Q., Manilla, A. A. S., López-Yáñez, I., Sun, G.-H., & Dong, S. (2019) · Physica Scripta · doi:10.1088/1402-4896/ab2111 · Cited by 21
Computations with greater Quantum depth are strictly more powerful (relative to an oracle)
Coudron, M., & Menda, S. (2020) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3357713.3384269 · Cited by 21
Fenner, S., Fortnow, L., Kurtz, S. A., & Li, L. (2003) · Information and Computation · doi:10.1016/s0890-5401(03)00018-x · Cited by 24
Winter, A. (2002) · Journal of Mathematical Physics · doi:10.1063/1.1498489 · Cited by 22
Basic Properties of Quantum Automata
Gudder, S. (2000) · Foundations of Physics · doi:10.1023/a:1003649201735 · Cited by 21
Gudder, S. (1999) · International Journal of Theoretical Physics · doi:10.1023/a:1026663432352 · Cited by 20
Does Rydberg State Manipulation Equal Quantum Computation?
MEYER, D. A. (2000) · Science · doi:10.1126/science.289.5484.1431a · Cited by 21
An Introduction to Quantum Game TheoryPreprint
Grabbe, J. O. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0506219 · Cited by 30
Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT dualityPreprint
Bouland, A., Fefferman, B., & Vazirani, U. V. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1910.14646 · Cited by 46
Self-citationQuantum algorithms for scientific computing
Au-Yeung, R., Camino, B., Rathore, O., & Kendon, V. M. (2024) · Reports on Progress in Physics · doi:10.1088/1361-6633/ad85f0 · Cited by 37
Human Rationality Challenges Universal Logic
Gaines, B. R. (2010) · Logica Universalis · doi:10.1007/s11787-010-0019-9 · Cited by 21
A theoretical framework for quantum image representation and data loading scheme
Hu, B.-Q., Huang, X., Zhou, R., Wei, Y., Wan, Q., & Pang, C.-Y. (2014) · Science China Information Sciences · doi:10.1007/s11432-013-4866-x · Cited by 23
Quantum algorithms: A survey of some recent results
Rötteler, M. (2006) · Informatik - Forschung und Entwicklung · doi:10.1007/s00450-006-0008-7 · Cited by 20
Superiority of one-way and realtime quantum machines
Yakaryılmaz, A. (2012) · RAIRO - Theoretical Informatics and Applications · doi:10.1051/ita/2012018 · Cited by 20
An Improved Filtering Method for Quantum Color Image in Frequency Domain
Li, P., & Xiao, H. Y. (2017) · International Journal of Theoretical Physics · doi:10.1007/s10773-017-3561-x · Cited by 20
Quantum Simulation Logic, Oracles, and the Quantum Advantage
Johansson, N., & Larsson, J.-Å. (2019) · Entropy · doi:10.3390/e21080800 · Cited by 25
Stochastic Analog Networks and Computational Complexity
Siegelmann, H. T. (1999) · Journal of Complexity · doi:10.1006/jcom.1999.0505 · Cited by 20
On a measurement-free quantum lambda calculus with classical control
Lago, U. D., Masini, A., & Zorzi, M. (2009) · Mathematical Structures in Computer Science · doi:10.1017/s096012950800741x · Cited by 21
A decision procedure for well-formed linear quantum cellular automata
Dürr, C., Thanh, H. L., & Sántha, M. (1996) · Lecture notes in computer science · doi:10.1007/3-540-60922-9_24 · Cited by 20
Berthiaume, A., & Brassard, G. (2005) · Workshop on Physics and Computation (PhysComp) · doi:10.1109/phycmp.1992.615538 · Cited by 21
Quantum and classical parallelism in parity algorithms for ensemble quantum computers
Stadelhofer, R., Suter, D., & Banzhaf, W. (2005) · Physical Review A · doi:10.1103/physreva.71.032345 · Cited by 21
Exact results for accepting probabilities of quantum automata
Ambainis, A., & Ķikusts, A. (2003) · Theoretical Computer Science · doi:10.1016/s0304-3975(02)00393-6 · Cited by 20
Unitarity in one dimensional nonlinear quantum cellular automataPreprint
MEYER, D. A. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9605023 · Cited by 21
The lambda-q calculus can efficiently simulate quantum computersPreprint
Maymin, P. Z. (1997) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9702057 · Cited by 21
Quantum classificationPreprint
Gambs, S. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0809.0444 · Cited by 21
Manenti, R., & Motta, M. (2023) · Oxford University Press eBooks · doi:10.1093/oso/9780198787488.005.0002 · Cited by 20
Quantum Differential Cryptanalysis to the Block Ciphers
Li, H., & Yang, L. (2015) · Communications in computer and information science · doi:10.1007/978-3-662-48683-2_5 · Cited by 20
Quantum forgery attacks on COPA, AES-COPA and marble authenticated encryption algorithms
Xu, Y., Liu, W., & Yu, W. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03036-w · Cited by 19
Optimal Mapping for Near-Term Quantum Architectures based on Rydberg Atoms
Brandhofer, S., Polian, I., & Büchler, H. P. (2021) · International Conference on Computer Aided Design · doi:10.1109/iccad51958.2021.9643490 · Cited by 22
A note on quantum sequential machines
Li, L., & Qiu, D. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.08.026 · Cited by 19
Rötteler, M. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03816-7_56 · Cited by 18
Quantum finite automata: Advances on Bertoni's ideas
Bianchi, M. P., Mereghetti, C., & Palano, B. (2016) · Theoretical Computer Science · doi:10.1016/j.tcs.2016.01.045 · Cited by 19
Corrigan-Gibbs, H., Wu, D. J., & Boneh, D. (2017) · Workshop on Hot Topics in Operating Systems · doi:10.1145/3102980.3102993 · Cited by 19
The query complexity of order-finding
Cleve, R. (2004) · Information and Computation · doi:10.1016/j.ic.2004.04.001 · Cited by 19
Svozil, K. (2016) · Ethics in Science and Environmental Politics · doi:10.3354/esep00171 · Cited by 19
Necessary and Sufficient Conditions for Quantum Computation
Lloyd, S. (1994) · Journal of Modern Optics · doi:10.1080/09500349414552341 · Cited by 19
Quantum algorithm for optical-template recognition with noise filtering
Schaller, G., & Schützhold, R. (2006) · Physical Review A · doi:10.1103/physreva.74.012303 · Cited by 21
The query complexity of order-finding
Cleve, R. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2000.856735 · Cited by 19
A Theory of Cartesian Arrays (with Applications in Quantum Circuit Verification)
Chen, Y., Rümmer, P., & Tsai, W.-L. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-38499-8_10 · Cited by 18
Quantum information processing, operational quantum logic, convexity, and the foundations of physics
Barnum, H. (2003) · Studies in History and Philosophy of Science Part B Studies in History and Philosophy of Modern Physics · doi:10.1016/s1355-2198(03)00033-9 · Cited by 20
Quantum Cryptography, Quantum Communication, and Quantum Computer in a Noisy Environment
Nagata, K., & Nakamura, T. (2017) · International Journal of Theoretical Physics · doi:10.1007/s10773-017-3352-4 · Cited by 18
Quantum Vs Classical Computing: a Comparative Analysis
Belkhir, M., Benkaouha, H., & Benkhelifa, E. (2022) · International Conference on Fog and Mobile Edge Computing (FMEC) · doi:10.1109/fmec57183.2022.10062753 · Cited by 22
The Impact of Quantum Computing on Cybersecurity
Emmanni, P. S. (2023) · Journal of Mathematical & Computer Applications · doi:10.47363/jmca/2023(2)140 · Cited by 28
Intrinsically universal n-dimensional quantum cellular automata
Arrighi, P. J., & Grattage, J. (2012) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2011.12.008 · Cited by 21
Copeland, B. J., & Shagrir, O. (2018) · Communications of the ACM · doi:10.1145/3198448 · Cited by 18
Uncomputability of phase diagrams
Bausch, J., Cubitt, T. S., & Watson, J. D. (2020) · RePEc: Research Papers in Economics · doi:10.17863/cam.63563 · Cited by 18
Brassard, G. (1994) · ACM SIGACT News · doi:10.1145/190616.190617 · Cited by 20
Berthiaume, A., van Dam, W., & Laplante, S. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2000.856755 · Cited by 19
Introduction to Quantum Information ProcessingPreprint
Knill, E. H., Laflamme, R., Barnum, H., Dalvit, D. A. R., Dziarmaga, J., Gubernatis, J. E., Gurvits, L., Ortíz, G., Viola, L., & Zurek, W. H. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0207171 · Cited by 27
A quantum related-key attack based on the Bernstein–Vazirani algorithm
Xie, H., & Yang, L. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02741-2 · Cited by 18
Quantum lower bound for inverting a permutation with advice
Nayebi, A., Aaronson, S., Belovs, A., & Trevisan, L. (2015) · Quantum Information and Computation · doi:10.26421/qic15.11-12-1 · Cited by 26
QMA variants with polynomially many provers
Gharibian, S., Sikora, J., & Upadhyay, S. (2013) · Quantum Information and Computation · doi:10.26421/qic13.1-2-8 · Cited by 20
Quantum counterfeit coin problems
Iwama, K., Nishimura, H., Raymond, R., & Teruyama, J. (2012) · Theoretical Computer Science · doi:10.1016/j.tcs.2012.05.039 · Cited by 17
Automata theory based on complete residuated lattice-valued logic: Turing machines
Wu, L., Qiu, D., & Xing, H. (2012) · Fuzzy Sets and Systems · doi:10.1016/j.fss.2012.03.001 · Cited by 17
A comparative study of universal quantum computing models: Toward a physical unification
Wang, D. (2021) · Quantum Engineering · doi:10.1002/que2.85 · Cited by 18
An improved lower bound on query complexity for quantum PAC learning
Zhang, C. (2010) · Information Processing Letters · doi:10.1016/j.ipl.2010.10.007 · Cited by 18
Upper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing
Kempe, J., Regev, O., Unger, F., & de Wolf, R. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-70575-8_69 · Cited by 16
Reasoning about Grover's quantum search algorithm using probabilistic wp
Butler, M. J., & Hartel, P. (1999) · ACM Transactions on Programming Languages and Systems · doi:10.1145/319301.319303 · Cited by 19
Algorithms for Boolean Function Query Properties
Aaronson, S. (2003) · SIAM Journal on Computing · doi:10.1137/s0097539700379644 · Cited by 20
Evolving blackbox quantum algorithms using genetic programming
Stadelhofer, R., Banzhaf, W., & Suter, D. (2008) · Artificial intelligence for engineering design analysis and manufacturing · doi:10.1017/s089006040800019x · Cited by 16
Robust Polynomials and Quantum Algorithms
Buhrman, H., Newman, I., Röhrig, H., & de Wolf, R. (2005) · Lecture notes in computer science · doi:10.1007/978-3-540-31856-9_49 · Cited by 17
Yamakami, T. (2003) · International Journal of Foundations of Computer Science · doi:10.1142/s0129054103002047 · Cited by 19
Scalable Circuit Cutting and Scheduling in a Resource-Constrained and Distributed Quantum System
Kan, S., Du, Z., Palma, M., Stein, S. A., Liu, C., Wei, W., Chen, J., Li, A., & Mao, Y. (2024) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce60285.2024.00127 · Cited by 16
A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY
Yamakami, T. (2020) · Journal of Symbolic Logic · doi:10.1017/jsl.2020.45 · Cited by 16
Memristor Hardware Accelerator of Quantum Computations
Fyrigos, I.-A., Ntinas, V. G., Sirakoulis, G. C., Dimitrakis, P., & Karafyllidis, I. G. (2019) · IEEE International Conference on Electronics, Circuits and Systems (ICECS) · doi:10.1109/icecs46596.2019.8965109 · Cited by 16
Quantum logic and automata theory
Ying, M. (2007) · Elsevier eBooks · doi:10.1016/b978-044452870-4/50037-6 · Cited by 16
Confluence Results for a Quantum Lambda Calculus with Measurements
Lago, U. D., Masini, A., & Zorzi, M. (2011) · Electronic Notes in Theoretical Computer Science · doi:10.1016/j.entcs.2011.01.035 · Cited by 16
Applying evolutionary techniques to quantum computing problems
Hutsell, S. R., & Greenwood, G. W. (2007) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2007.4425003 · Cited by 16
Nishimura, H., & Ozawa, M. (2009) · Quantum Information Processing · doi:10.1007/s11128-008-0091-8 · Cited by 20
A decision procedure for unitary linear quantum cellular automata
Dürr, C., & Sántha, M. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1996.548462 · Cited by 16
Operational semantics for formal tensorial calculus
Arrighi, P. J., & Gilles Dowek, B. (2004) · Cited by 16
Quantum Computing, NP-complete Problems and Chaotic DynamicsPreprint
Ohya, M., & Volovich, I. V. (1999) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9912100 · Cited by 20
On the learnability of quantum neural networksPreprint
Du, Y., Hsieh, M.-H., Liu, T., You, S., & Tao, D. (2020) · Research Square · doi:10.21203/rs.3.rs-80242/v1 · Cited by 18
Aaronson, S., Bouland, A., Fitzsimons, J. F., & Lee, M. (2016) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2840728.2840739 · Cited by 15
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
