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
Items 901–1,000 of 1,000
QPlacer: Frequency-Aware Component Placement for Superconducting Quantum Computers
Zhang, J., Wang, H., Ding, Q., Gu, J., Assouly, R., Oliver, W. D., Han, S., Brown, K. R., Li, H. H., & Chen, Y. (2025) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/3695053.3730994 · Cited by 10
Translation of Quantum Circuits into Quantum Turing Machines for Deutsch and Deutsch-Jozsa Problems
Corrente, G. (2020) · Journal of quantum computing · doi:10.32604/jqc.2020.014586 · Cited by 2
Bhattacharyya, M., & Raina, A. (2026) · Quantum Information Processing · doi:10.1007/s11128-026-05074-8 · Cited by 2
Evolutionary Logic Synthesis of Quantum Finite State Machines for Sequence Detection
Lukáč, M., & Perkowski, M. A. (2010) · InTech eBooks · doi:10.5772/8049 · Cited by 2
The Quantum Computing Challenge
Vitanyi, P. M. B. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44577-3_15 · Cited by 2
A Formal Technique for Reducing Software Testing Time Complexity
Baig, M. M., & Khan, A. A. (2009) · Springer eBooks · doi:10.1007/978-90-481-3658-2_34 · Cited by 2
Improved Algorithms for Quantum Identification of Boolean Oracles
Ambainis, A., Iwama, K., Kawachi, A., Raymond, R., & Yamashita, S. (2006) · Lecture notes in computer science · doi:10.1007/11785293_27 · Cited by 2
A Novel Kind of Architecture with High-Efficiency and Error-Tolerance of Universal Quantum Computer
Nan, W. U., & Song, F. (2009) · Chinese Journal of Computers · doi:10.3724/sp.j.1016.2009.00161 · Cited by 2
Study of a Quantum Framework for Search Based Software Engineering
Wu, N., Song, F., & Li, X. (2013) · International Journal of Theoretical Physics · doi:10.1007/s10773-013-1544-0 · Cited by 2
Quantum Mechanics and Computation
D’Hooghe, B., & Pykacz, J. (2004) · Foundations of Science · doi:10.1007/s10699-005-4827-y · Cited by 2
Qiu, D., Li, L., Mateus, P., & Gruska, J. (2012) · Chapman & Hall/CRC eBooks · doi:10.1201/b13055-11 · Cited by 2
ON THE PRACTICALITY OF ADIABATIC QUANTUM COMPUTING WITH OPTICAL SCHEMES
Goswami, D. (2007) · International Journal of Quantum Information · doi:10.1142/s0219749907002621 · Cited by 2
Resource Restricted Computability Theoretic Learning: Illustrative Topics and Problems
Case, J. (2009) · Theory of Computing Systems · doi:10.1007/s00224-009-9169-7 · Cited by 2
Implementing associative memory with quantum neural networks
Zhao, J. (2005) · International Conference on Machine Learning and Cybernetics · doi:10.1109/icmlc.2004.1378586 · Cited by 2
Data Analytics in Quantum Paradigm: An Introduction
Maitra, A., Maitra, S., & Pal, A. K. (2017) · Springer eBooks · doi:10.1007/978-3-319-54840-1_15 · Cited by 2
Monroe, D. (2018) · Communications of the ACM · doi:10.1145/3290407 · Cited by 2
Quantum lower bound for recursive Fourier sampling
Aaronson, S. (2005) · Quantum Information and Computation · doi:10.26421/qic5.2-9 · Cited by 2
Remarks on the Structure of Clifford Quantum Cellular Automata
Schlingemann, D.-M. (2009) · Open Systems & Information Dynamics · doi:10.1142/s1230161209000207 · Cited by 2
Sun, X. (2016) · Scientia Sinica Informationis · doi:10.1360/n112016-00084 · Cited by 2
Nagata, K., Wong, R., Diep, D. N., & Nakamura, T. (2023) · Quantum Studies Mathematics and Foundations · doi:10.1007/s40509-023-00294-4 · Cited by 2
Quantum Cryptography, Quantum Communication, and Quantum Computing in a Noisy Environment
Nagata, K., Nakamura, T., & Farouk, A. (2017) · Studies in big data · doi:10.1007/978-3-319-63639-9_8 · Cited by 2
Computational complexity in high-dimensional quantum computing
Nagata, K., Diep, D. N., & Nakamura, T. (2022) · Quantum Machine Intelligence · doi:10.1007/s42484-022-00084-y · Cited by 2
Vathsan, R. (2015) · CRC Press eBooks · doi:10.1201/b18767-17 · Cited by 3
A user-centric quantum benchmarking test suite and evaluation framework
Liu, W., Wang, F., Lin, H., & Shang, J. (2023) · Quantum Information Processing · doi:10.1007/s11128-023-04154-3 · Cited by 2
Efficient quantum algorithms for set operations
Elgendy, R., Younes, A., Abu-Donia, H. M., & Farouk, R. M. (2024) · Scientific Reports · doi:10.1038/s41598-024-56860-2 · Cited by 2
Mathematics for Quantum Information Processing
Hirvensalo, M. (2012) · Springer eBooks · doi:10.1007/978-3-540-92910-9_41 · Cited by 2
Yamakami, T. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45833-6_25 · Cited by 2
Ulyanoy, S. V., Antoni, G. D., Yamafuji, K., Fukuda, T., Rizzotto, G., & Kurawaki, I. (2002) · International Symposium on Micro-NanoMechatronics and Human Science · doi:10.1109/mhs.1998.745785 · Cited by 3
Alan Turing y los orígenes de la complejidad
Martin-Delgado, M. A. (2013) · Arbor · doi:10.3989/arbor.2013.764n6006 · Cited by 2
Fuzzy Kolmogorov Complexity Based on a Classical Description
Dai, S. (2020) · Entropy · doi:10.3390/e22010066 · Cited by 2
An Exact Quantum Algorithm for a Restricted Subtraction Game
Huang, Y., Ye, Z., Zheng, S., & Li, L. (2020) · International Journal of Theoretical Physics · doi:10.1007/s10773-020-04418-z · Cited by 2
Combarro, E. F., Nicolás, A. P., Ranilla, J., & Rúa, I. F. (2020) · Computational and Mathematical Methods · doi:10.1002/cmm4.1120 · Cited by 2
Automata and quantum computing
Ambainis, A., & Yakaryılmaz, A. (2021) · doi:10.4171/automata-1/39 · Cited by 2
How Many Query Superpositions Are Needed to Learn?
Castro, J. (2006) · Lecture notes in computer science · doi:10.1007/11894841_10 · Cited by 2
Information Hypothesis: On Human Information Capability Study
Krajíček, J. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-04954-5_13 · Cited by 2
Scale decoherence in inhomogeneous potentialsPreprint
Meyer, D. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9805039 · Cited by 5
Historical Bibliography of Quantum Computing
Cirasella, J. (2008) · Cambridge University Press eBooks · doi:10.1017/cbo9780511813887.014 · Cited by 2
Classical Simulation Complexity of Quantum Machines
Ablayev, F. M., & Gainutdinova, A. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45077-1_27 · Cited by 2
An exponential time upper bound for Quantum Merlin-Arthur games with unentangled proversPreprint
Schwarz, M. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1510.08447 · Cited by 2
QUANTUM COMPUTATION WITH RESTRICTED AMPLITUDES
Nishimura, H. (2003) · International Journal of Foundations of Computer Science · doi:10.1142/s0129054103002059 · Cited by 2
Measurement of an integral of a classical field with a single quantum particle
Lev Vaidman, A., & Kalev, A. (2005) · Physical Review A · doi:10.1103/physreva.71.044303 · Cited by 2
Quantum Algorithms and Complexity for Continuous Problems
(2011) · Springer eBooks · doi:10.1007/springerreference_60596 · Cited by 2
Quantum ComputationPreprint
Bishnoi, B. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2006.02799 · Cited by 7
Jones, C. (2020) · PsyArXiv (OSF Preprints) · doi:10.31234/osf.io/gbmk6 · Cited by 2
On using probabilistic Turing machines to model participants in cryptographic protocols
Klingler, L., Steinwandt, R., & Unruh, D. (2013) · Theoretical Computer Science · doi:10.1016/j.tcs.2013.05.015 · Cited by 1
A Quantum Cellular Automata Type Architecture with Quantum Teleportation for Quantum Computing
Ntalaperas, D., Giannakis, K., & Konofaos, N. (2019) · Entropy · doi:10.3390/e21121235 · Cited by 1
How does adiabatic quantum computation fit into quantum automata theory?
Yamakami, T. (2021) · Information and Computation · doi:10.1016/j.ic.2021.104694 · Cited by 1
Card Game to Demonstrate Quantum Key Exchange
Ferner, C. S. (2023) · IT Professional · doi:10.1109/mitp.2023.3279688 · Cited by 1
Phase Coordinate Uncomputation in Quantum Recursive Fourier Sampling
Hindlycke, C., Johansson, N., & Larsson, J.-Å. (2025) · Entropy · doi:10.3390/e27060596 · Cited by 1
Quantum Programming Without the Quantum Physics
Inoue, J. (2024) · Lecture notes in computer science · doi:10.1007/978-981-97-8943-6_8 · Cited by 1
Classification Using Hybrid Classical-Quantum Machine Learning
Bala, R., Kher, G., Singh, V., & Singh, R. (2025) · Communications in computer and information science · doi:10.1007/978-3-031-84059-3_14 · Cited by 1
Zhou, X., Wang, Y., Tao, W., Zhou, Z., & Luo, L. (2025) · Advanced Quantum Technologies · doi:10.1002/qute.202500067 · Cited by 1
Quantum Computing-The Underlying Principle Behind it
Chawla, A., Mathur, S., Rao, H., Mudgal, N., & Bhardwaj, V. (2025) · Prabha Materials Science Letters · doi:10.33889/pmsl.2025.4.2.020 · Cited by 1
DevQCC: Device-Aware Quantum Circuit Cutting framework with applications in quantum machine learning
Sahu, H., Gupta, H. P., Puvvada, V. V., & Mishra, R. (2025) · Quantum Machine Intelligence · doi:10.1007/s42484-025-00313-0 · Cited by 2
Classical Algorithms for Measurement-Adaptive Gaussian Circuits
Oh, C., & Lim, Y. (2026) · PRX Quantum · doi:10.1103/rpl7-ylg8 · Cited by 3
Quantum advantage for learning shallow neural networks with natural data distributions
Lewis, L., Gilboa, D., & McClean, J. R. (2025) · Nature Communications · doi:10.1038/s41467-025-68097-2 · Cited by 8
Pierro, A. D., & Panarotto, F. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-44145-9_11 · Cited by 1
Reexamination of quantum data compression and relative entropy
Kaltchenko, A. (2008) · Physical Review A · doi:10.1103/physreva.78.022311 · Cited by 1
Quantum Computation Relative to Oracles
Tamon, C., & Yamakami, T. (2001) · Springer eBooks · doi:10.1007/978-1-4471-0313-4_20 · Cited by 1
Quantum model of computations: Underlying principles and achievements
Anisimov, A. V., & Danil’chenko, S. V. (2000) · Cybernetics and Systems Analysis · doi:10.1007/bf02733301 · Cited by 1
Walsh transforms and efficient quantum algorithms
Mihara, T. (2000) · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · doi:10.1002/(sici)1520-6440(200008)83:8 · Cited by 1
Quantum protocols for untrusted computations
Mihara, T. (2006) · Journal of Discrete Algorithms · doi:10.1016/j.jda.2006.03.007 · Cited by 1
The Search for Structure in Quantum Computation
Panangaden, P. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-19805-2_1 · Cited by 1
Efficient quantum circuits for approximating the Jones polynomial
Yumi Nakajima, A., Kawano, Y., & Sekigawa, H. (2008) · Quantum Information and Computation · doi:10.26421/qic8.5-8 · Cited by 1
CLS QTM: New Model of Node Configuration In Collaboration Learning Systems By Quantum Turing Machine
Bahrami, M., & Pashaie, L. (2011) · International Journal of Advancements in Computing Technology · doi:10.4156/ijact.vol3.issue7.18 · Cited by 1
Undecidability of the Criterion for Recognizing the Fibonacci Numbers
Bolotin, A. (2015) · British Journal of Mathematics & Computer Science · doi:10.9734/bjmcs/2015/19785 · Cited by 1
Information and Conditional Probability to Go beyond Hidden Variables
Nagata, K., Resconi, G., Nakamura, T., & Geurdes, H. J. F. (2016) · Journal of Applied Mathematics and Physics · doi:10.4236/jamp.2016.412214 · Cited by 1
The Quantum Sieve of Eratosthenes
Sowa, A. (2016) · Journal of Physical Mathematics · doi:10.4172/2090-0902.1000180 · Cited by 1
Computational Complexity Study of RSA and Elgamal Algorithms
Okeyinka, A. E. (2017) · Springer eBooks · doi:10.1007/978-981-10-2717-8_17 · Cited by 1
Quantum Communication Based on an Algorithm of Determining a Matrix
Nagata, K., & Nakamura, T. (2018) · International Journal of Theoretical Physics · doi:10.1007/s10773-018-3926-9 · Cited by 1
Arias, D., Sanz, B., de la Puerta, J. G., Pastor-López, I., & Bringas, P. G. (2021) · Advances in intelligent systems and computing · doi:10.1007/978-3-030-87872-6_16 · Cited by 1
Interrelation of nonclassicality conditions through stabiliser group homomorphism
Asthana, S. (2022) · New Journal of Physics · doi:10.1088/1367-2630/ac6900 · Cited by 1
An exact quantum hidden subgroup algorithm and applications to solvable groups
Imran, M., & Ivanyos, G. (2022) · Quantum Information and Computation · doi:10.26421/qic22.9-10-4 · Cited by 1
Phillipson, F. (2022) · doi:10.26481/spe.20220525fp · Cited by 1
Luchnikov, I. A., Tatarkin, O. E., & Fedorov, A. K. (2023) · AIP conference proceedings · doi:10.1063/5.0166887 · Cited by 1
Quantum Process Tomography on Cloud-accessible Quantum Computing Platforms
Ведруков, П. Е., Ivlev, A. D., Liniov, A., Meyerov, I. B., & Ivanchenko, M. (2024) · Lobachevskii Journal of Mathematics · doi:10.1134/s1995080224010529 · Cited by 1
Zhang, K., Shang, T., Tang, Y., & Liu, J. (2024) · Quantum Information Processing · doi:10.1007/s11128-024-04491-x · Cited by 1
Deutsch-Jozsa and Bernstein-Vazirani algorithm using single-particle discrete-time quantum walk
Sangwan, R., Ramaswamy, V., Sukumar, H., & Raghava, G. N. (2025) · IEEE International Conference on Electronics, Computing and Communication Technologies (CONECCT) · doi:10.1109/conecct65861.2025.11306771 · Cited by 2
Quantum Computers and Quantum Automata
Freivalds, R. (2000) · Springer eBooks · doi:10.1007/978-1-4757-6048-4_44 · Cited by 1
Deterministic Application of Grover’s Quantum Search Algorithm
Okamoto, K., & Watanabe, O. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44679-6_55 · Cited by 1
Quantum Attacks on ECDLP-Based Cryptosystems
Yan, S. Y. (2013) · Springer eBooks · doi:10.1007/978-1-4419-7722-9_4 · Cited by 1
Revisiting a limit on efficient quantum computation
Purewal, T. S. (2006) · ACM Southeast Regional Conference (ACMSE) · doi:10.1145/1185448.1185502 · Cited by 1
Ohya, M., & Volovich, I. V. (2011) · Theoretical and mathematical physics · doi:10.1007/978-94-007-0171-7_14 · Cited by 1
On a class of quantum Turing machine halting deterministically
Liang, M., & Yang, L. (2013) · Science China Physics Mechanics and Astronomy · doi:10.1007/s11433-013-5048-y · Cited by 1
Time in the Analysis of Algorithms
Furia, C. A., Mandrioli, D., Morzenti, A., & Rossi, M. (2012) · Monographs in theoretical computer science · doi:10.1007/978-3-642-32332-4_6 · Cited by 1
Classical and Quantum Computation
Yan, S. Y. (2015) · Springer eBooks · doi:10.1007/978-3-319-25823-2_2 · Cited by 1
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0012 · Cited by 1
QM Automata: A New Class of Restricted Quantum Membrane Automata
Giannakis, K., Singh, A., Kastampolidou, K., Papalitsas, C., & Andronikos, T. (2017) · Advances in experimental medicine and biology · doi:10.1007/978-3-319-56246-9_15 · Cited by 1
“Quantumness” versus “classicality” of quantum states and quantum protocols
Brodutch, A., Groisman, B., Kenigsberg, D., & Mor, T. (2018) · International Journal of Quantum Information · doi:10.1142/s0219749918500144 · Cited by 1
Quantum query complexity of symmetric oracle problems
Copeland, D., & Pommersheim, J. (2021) · Quantum · doi:10.22331/q-2021-03-07-403 · Cited by 4
Energy transfer and thermodynamics of quantum gravity computation
Gyöngyösi, L. (2020) · Chaos Solitons & Fractals X · doi:10.1016/j.csfx.2020.100050 · Cited by 1
Yamakami, T. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-87993-8_12 · Cited by 1
Developing a Hardware Approach to Simulating Quantum Computing Using an Optimization Algorithm
Николаевич, П. В., Gushanskiy, S. M., & Potapov, V. (2021) · Panhellenic Conference on Informatics · doi:10.1145/3503823.3503894 · Cited by 1
Mathematical Models of Quantum Computer
Ohya, M., & Volovich, I. V. (2011) · Theoretical and mathematical physics · doi:10.1007/978-94-007-0171-7_11 · Cited by 1
Resource Restricted Computability Theoretic Learning: Illustrative Topics and Problems
Case, J. (2007) · Lecture notes in computer science · doi:10.1007/978-3-540-73001-9_12 · Cited by 1
Two-player interaction in quantum computing : cryptographic primitives & query complexity
Magnin, L. (2011) · theses.fr (ABES) · doi:10.70675/7fd872caz151az4eadzb0f5zc53f4c46586d · Cited by 1
Quantum Computing: A Way to Break Complexity?
Gesù, V. D., & Palma, G. M. (2003) · Springer eBooks · doi:10.1007/978-94-010-0155-7_21 · Cited by 1
An Eigenanalysis and Synthesis of Unitary Operators used in Quantum Computing Algorithms
Hutsell, S. T. (2000) · doi:10.15760/etd.251 · Cited by 1
A Review of Procedure to Evolve Quantum ProceduresPreprint
Gepp, A., & Stocks, P. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0708.3278 · Cited by 1
Yamakami, T. (2016) · Baltic Journal of Modern Computing · doi:10.22364/bjmc.2016.4.4 · Cited by 1
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
