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 501–600 of 1,000
Wave-Style Token Machines and Quantum Lambda Calculi
Lago, U. D., & Zorzi, M. (2015) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.176.6 · Cited by 15
Matsui, N., Nishimura, H., & Isokawa, T. (2009) · IGI Global eBooks · doi:10.4018/978-1-60566-214-5.ch013 · Cited by 15
The Road to Quantum Computational Supremacy
Calude, C. S., & Calude, E. (2020) · Springer proceedings in mathematics & statistics · doi:10.1007/978-3-030-36568-4_22 · Cited by 22
Quantum algorithms on Walsh transform and Hamming distance for Boolean functions
Xie, Z., Qiu, D., & Cai, G. (2018) · Quantum Information Processing · doi:10.1007/s11128-018-1885-y · Cited by 15
Massively Parallel Approximate Simulation of Hard Quantum Circuits
Markov, I. L., Fatima, A., Isakov, S. V., & Boixo, S. (2020) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1109/dac18072.2020.9218591 · Cited by 15
Digital-Analog Quantum Simulation of Fermionic Models
Céleri, L. C., Huerga, D., Albarrán-Arriagada, F., Solano, E., de Andoin, M. G., & Sanz, M. (2023) · Physical Review Applied · doi:10.1103/physrevapplied.19.064086 · Cited by 15
Brandhofer, S., Devitt, S. J., Wellens, T., & Polian, I. (2021) · IEEE VLSI Test Symposium (VTS) · doi:10.1109/vts50974.2021.9441047 · Cited by 15
A prototype of quantum von Neumann architecture
Wang, D. (2022) · Communications in Theoretical Physics · doi:10.1088/1572-9494/ac68d8 · Cited by 15
Quantum algorithms for testing Boolean functions
Floess, D., Andersson, E., & Hillery, M. S. (2010) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.26.9 · Cited by 15
Improved algorithms for quantum identification of Boolean oracles
Ambainis, A., Iwama, K., Kawachi, A., Raymond, R., & Yamashita, S. (2006) · Theoretical Computer Science · doi:10.1016/j.tcs.2006.12.013 · Cited by 16
Testing shift-equivalence of polynomials using quantum machines
Grigoriev, D. Y. (1996) · International Symposium on Symbolic and Algebraic Computation · doi:10.1145/236869.236897 · Cited by 15
High Fidelity Quantum Gates with Vibrational Qubits
Berríos, E., Gruebele, M., Shyshlov, D., Wang, L., & Babikov, D. (2012) · The Journal of Physical Chemistry A · doi:10.1021/jp3055729 · Cited by 15
Quantum NP and a Quantum Hierarchy
Yamakami, T. (2002) · Springer eBooks · doi:10.1007/978-0-387-35608-2_27 · Cited by 17
How a Clebsch-Gordan transform helps to solve the Heisenberg hidden subgroup problem
Bacon, D. (2008) · Quantum Information and Computation · doi:10.26421/qic8.5-6 · Cited by 15
The Fourier spectrum of critical percolation
Garban, C., Pete, G., & Schramm, O. (2011) · Springer eBooks · doi:10.1007/978-1-4419-9675-6_14 · Cited by 15
Quantum Search on Structured Problems
Grover, L. K. (1999) · Lecture notes in computer science · doi:10.1007/3-540-49208-9_9 · Cited by 15
Relationships between quantum and classical space-bounded complexity classes
Watrous, J. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.1998.694607 · Cited by 13
A Rosetta Stone for quantum mechanics with an introduction to quantum computation
Lomonaco, S. J. (2002) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/058/1922894 · Cited by 14
A space-efficient quantum computer simulator suitable for high-speed FPGA implementation
Frank, M. P., Oniciuc, L., Meyer-Baese, U. H., & Chiorescu, I. (2009) · SPIE Proceedings · doi:10.1117/12.817924 · Cited by 14
Simulating fermions on a quantum computer
Ortíz, G., Gubernatis, J. E., Knill, E. H., & Laflamme, R. (2002) · Computer Physics Communications · doi:10.1016/s0010-4655(02)00421-6 · Cited by 14
Undecidability of the Spectral Gap
Cubitt, T. S., Pérez-Garcı́a, D., & Wolf, M. M. (2022) · Forum of Mathematics Pi · doi:10.1017/fmp.2021.15 · Cited by 14
A Deep Inside Quantum Technology Industry Trends and Future Implications
Putranto, D. S. C., Wardhani, R. W., Ji, J., & Kim, H. (2024) · IEEE Access · doi:10.1109/access.2024.3444779 · Cited by 14
Verifying Quantum Circuits with Level-Synchronized Tree Automata
Abdulla, P. A., Chen, Y. C., Chen, Y., Holík, L., Lengál, O., Lin, J.-A., Lo, F.-Y., & Tsai, W.-L. (2025) · Proceedings of the ACM on Programming Languages · doi:10.1145/3704868 · Cited by 29
Extending scientific computing system with structural quantum programming capabilities
Gawron, P., Klamka, J., Miszczak, J. A., & Winiarczyk, R. (2009) · Cited by 14
A quantum distinguisher for 7/8-round SMS4 block cipher
Hodžić, S., & Knudsen, L. R. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02929-6 · Cited by 14
Quantum key-recovery attack on Feistel constructions: Bernstein–Vazirani meet Grover algorithm
Zhou, B.-M., & Yuan, Z. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03256-0 · Cited by 14
Fuzzy Turing Machines: Variants and Universality
Li, Y. (2008) · IEEE Transactions on Fuzzy Systems · doi:10.1109/tfuzz.2008.2004990 · Cited by 14
Nonadaptive quantum query complexity
Montanaro, A. (2010) · Information Processing Letters · doi:10.1016/j.ipl.2010.09.009 · Cited by 16
Tetrapartite entanglement measures of GHZ state with nonuniform acceleration
Dong, Q., Sun, G.-H., Toutounji, M. M., & Dong, S. (2019) · Optik · doi:10.1016/j.ijleo.2019.163487 · Cited by 14
Some Theoretically Organized Algorithm for Quantum Computers
Nagata, K., & Nakamura, T. (2019) · International Journal of Theoretical Physics · doi:10.1007/s10773-019-04354-7 · Cited by 14
An upper bound on the threshold quantum decoherence rate
Razborov, A. A. (2004) · Quantum Information and Computation · doi:10.26421/qic4.3-7 · Cited by 14
A theory of computation based on quantum logic (I)
Ying, M. (2005) · IEEE International Conference on Granular Computing (GrC) · doi:10.1109/grc.2005.1547240 · Cited by 14
Quantum Optimization Algorithms in Operations Research: Methods, Applications, and ImplicationsPreprint
Klug, F. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4854668 · Cited by 18
Manenti, R., & Motta, M. (2023) · doi:10.1093/oso/9780198787488.001.0001 · Cited by 15
Watrous, J. (2011) · ACM SIGACT News · doi:10.1145/1998037.1998053 · Cited by 14
The complexity of translationally invariant low-dimensional spin lattices in 3D
Bausch, J., & Piddock, S. (2017) · Journal of Mathematical Physics · doi:10.1063/1.5011338 · Cited by 13
Blind quantum machine learning based on quantum circuit model
Zhou, X., & Qiu, D. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03301-y · Cited by 13
Maitra, S., & MUKHOPADHYAY, P. (2005) · International Journal of Quantum Information · doi:10.1142/s0219749905000980 · Cited by 13
Quantum algorithms for graph problems with cut queries
Lee, T., Sántha, M., & Zhang, S. (2021) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611976465.59 · Cited by 13
Deterministic polynomial-time quantum algorithms for Simon?s problem
Mihara, T., & Sung, S. C. (2003) · Computational Complexity · doi:10.1007/s00037-003-0181-z · Cited by 13
One Complexity Theorist's View of Quantum Computing
Fortnow, L. (2000) · Electronic Notes in Theoretical Computer Science · doi:10.1016/s1571-0661(05)80330-5 · Cited by 15
Separating Quantum and Classical Learning
Servedio, R. A. (2001) · Lecture notes in computer science · doi:10.1007/3-540-48224-5_86 · Cited by 13
MEYER, D. A. (2002) · Computer Physics Communications · doi:10.1016/s0010-4655(02)00420-4 · Cited by 13
Quantum Computers Speed Up Classical with Probability ZeroPreprint
Ozhigov, Y. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9803064 · Cited by 17
Alternative Computational Models: A Comparison of Biomolecular and Quantum Computation
Reif, J. H. (1998) · Lecture notes in computer science · doi:10.1007/978-3-540-49382-2_10 · Cited by 12
The Measurement CalculusPreprint
Vincent Danos, A., Kashefi, E., & Panangaden, P. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.0704.1263 · Cited by 13
A Computability Argument Against Superintelligence
Wiedermann, J. (2012) · Cognitive Computation · doi:10.1007/s12559-012-9124-9 · Cited by 12
Classically-controlled Quantum Computation
Perdrix, S., & Jorrand, P. (2006) · Electronic Notes in Theoretical Computer Science · doi:10.1016/j.entcs.2005.09.026 · Cited by 12
Martin-Löf random quantum states
Nies, A., & Scholz, V. B. (2019) · Journal of Mathematical Physics · doi:10.1063/1.5094660 · Cited by 12
On the Hardness of PAC-learning Stabilizer States with Noise
Gollakota, A., & Liang, D. (2022) · Quantum · doi:10.22331/q-2022-02-02-640 · Cited by 12
Theory of quasi-exact fault-tolerant quantum computing and valence-bond-solid codes
Wang, D., Wang, Y.-J., Cao, N., Zeng, B., & Laflamme, R. (2021) · New Journal of Physics · doi:10.1088/1367-2630/ac4737 · Cited by 12
Toward Quantum Computational Agents
Klusch, M. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-25928-2_14 · Cited by 12
The Complexity of Black-Box Ring Problems
Arvind, V., Das, B., & Mukhopadhyay, P. (2006) · Lecture notes in computer science · doi:10.1007/11809678_15 · Cited by 12
The quantum query complexity of learning multilinear polynomials
Montanaro, A. (2012) · Information Processing Letters · doi:10.1016/j.ipl.2012.03.002 · Cited by 12
A public key cryptosystem based on data complexity under quantum environment
Wu, W., Zhang, H., Wang, H., Mao, S., Jia, J., & Liu, J. (2015) · Science China Information Sciences · doi:10.1007/s11432-015-5408-5 · Cited by 12
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-3 · Cited by 12
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.5555/2685155.2685156 · Cited by 14
Quantum Algorithms for Highly Structured Search Problems
Hunziker, M., & Meyer, D. (2002) · Quantum Information Processing · doi:10.1023/a:1019868924061 · Cited by 12
Quantum Computing for Computer Architects, Second Edition
Metodi, T. S., Faruque, A. I., & Chong, F. T. (2011) · Synthesis lectures on computer architecture · doi:10.1007/978-3-031-01731-5 · Cited by 15
SECOND QUANTIZED KOLMOGOROV COMPLEXITY
Rogers, C., Vedral, V., & Nagarajan, R. (2008) · International Journal of Quantum Information · doi:10.1142/s021974990800375x · Cited by 12
Optical implementations, oracle equivalence, and the Bernstein-Vazirani algorithm
Arvind, Kaur, G., & Narang, G. (2007) · Journal of the Optical Society of America B · doi:10.1364/josab.24.000221 · Cited by 12
Quantum programming: From theories to implementations
Ying, M., Feng, Y., Duan, R., Li, Y., & Yu, N. (2012) · Chinese Science Bulletin · doi:10.1007/s11434-012-5147-6 · Cited by 12
Rapid sampling though quantum computing
Grover, L. K. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335389 · Cited by 12
A proof that measured data and equations of quantum mechanics can be linked only by guesswork
Myers, J. M., & Madjid, F. H. (2002) · Contemporary mathematics - American Mathematical Society · doi:10.1090/conm/305/05222 · Cited by 12
Polynomial Simulations of Decohered Quantum ComputersPreprint
Aharonov, D., & Ben-Or, M. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9611029 · Cited by 20
Quantum Computing Solution of DC Power FlowPreprint
Eskandarpour, R., Ghosh, K., Khodaei, A., Zhang, L., Paaso, E. A., & Bahramirad, S. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.02442 · Cited by 12
Fast Universal Entangling Gate for Superconducting Quantum ComputersPreprint
AbuGhanem, M., Homid, A. H., Hendy, A. S., Obada, A. ‐. F., & Eleuch, H. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4726035 · Cited by 12
Boolean approach to dichotomic quantum measurement theories
Nagata, K., Nakamura, T., Batle, J. A. I., Abdalla, S., & Farouk, A. (2017) · Journal of the Korean Physical Society · doi:10.3938/jkps.70.229 · Cited by 11
Correlation measure equivalence in dynamic causal structures of quantum gravity
Gyöngyösi, L. (2020) · Quantum Engineering · doi:10.1002/que2.30 · Cited by 11
Eliminating Redundant Computation in Noisy Quantum Computing Simulation
Li, G., Ding, Y., & Xie, Y. (2020) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1109/dac18072.2020.9218666 · Cited by 11
Uncomputably complex renormalisation group flows
Watson, J. D., Onorati, E., & Cubitt, T. S. (2022) · Nature Communications · doi:10.1038/s41467-022-35179-4 · Cited by 11
Handling Non-unitaries in Quantum Circuit Equivalence Checking
Burgholzer, L., & Wille, R. (2022) · Springer eBooks · doi:10.1007/978-3-032-06770-8_18 · Cited by 16
Moore, C., & Mertens, S. (2011) · Oxford University Press eBooks · doi:10.1093/acprof:oso/9780199233212.003.0010 · Cited by 12
Improved BV-based quantum attack on block ciphers
Sun, H.-W., Wei, C., Cai, B., Qin, S., Wen, Q., & Gao, F. (2022) · Quantum Information Processing · doi:10.1007/s11128-022-03752-x · Cited by 11
Automated quantum software engineering
Sarkar, A. (2024) · Automated Software Engineering · doi:10.1007/s10515-024-00436-x · Cited by 14
On the complexity of the multivariate Sturm–Liouville eigenvalue problem
Papageorgiou, A. (2007) · Journal of Complexity · doi:10.1016/j.jco.2007.03.002 · Cited by 12
Programming Your Quantum Computer
Hayes, B. (2013) · American Scientist · doi:10.1511/2014.106.22 · Cited by 11
A fast quantum algorithm for the affine Boolean function identification
Younes, A. (2015) · The European Physical Journal Plus · doi:10.1140/epjp/i2015-15034-4 · Cited by 11
Lattice-valued fuzzy Turing machines: Computing power, universality and efficiency
Li, Y. (2009) · Fuzzy Sets and Systems · doi:10.1016/j.fss.2009.08.003 · Cited by 11
HADAMARD TYPE OPERATIONS FOR QUBITS
Maitra, A., & Parashar, P. (2006) · International Journal of Quantum Information · doi:10.1142/s0219749906002055 · Cited by 11
The Quantum Setting with Randomized Queries for Continuous Problems
Woźniakowski, H. (2006) · Quantum Information Processing · doi:10.1007/s11128-006-0013-6 · Cited by 11
Approximation and universality of fuzzy Turing machines
Li, Y. (2008) · Science in China Series F Information Sciences · doi:10.1007/s11432-008-0089-y · Cited by 11
Kocharovsky, V. V., Kocharovsky, V. V., & Tarasov, S. V. (2020) · Entropy · doi:10.3390/e22030322 · Cited by 11
Quantum Turing Machines: Local Transition, Preparation, Measurement, and Halting
Ozawa, M. (2005) · Kluwer Academic Publishers eBooks · doi:10.1007/0-306-47097-7_32 · Cited by 13
Polynomial-Time Algorithms for the Equivalence for One-Way Quantum Finite Automata
Koshiba, T. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45678-3_24 · Cited by 11
Efficient optical implementation of the Bernstein-Vazirani algorithm
Londero, P., Dorrer, C., Anderson, M. E., Wallentowitz, S., Banaszek, K., & Walmsley, I. A. (2004) · Physical Review A · doi:10.1103/physreva.69.010302 · Cited by 11
Quantum lower bound for the collision problem
Aaronson, S. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509998.509999 · Cited by 14
Pseudorandom generators and the BQP vs. PH problemPreprint
Fefferman, B., & Umans, C. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1007.0305 · Cited by 16
Universal quantum circuit of near-trivial transformations
Liang, M., & Yang, L. (2011) · Science China Physics Mechanics and Astronomy · doi:10.1007/s11433-011-4460-4 · Cited by 10
Hybrid quantum computing with ancillas
Proctor, T. J., & Kendon, V. M. (2016) · Contemporary Physics · doi:10.1080/00107514.2016.1152700 · Cited by 9
Faster and More Reliable Quantum SWAPs via Native Gates
Gokhale, P., Tomesh, T., Suchara, M., & Chong, F. T. (2024) · International Conference on Parallel Architectures and Compilation Techniques (PACT) · doi:10.1145/3656019.3689818 · Cited by 15
Universal Classical Optical Computing Inspired by Quantum Information Process
Sun, Y., Li, Q., Kong, L., Shang, J., & Zhang, X. (2022) · Annalen der Physik · doi:10.1002/andp.202200360 · Cited by 10
Maslov, D., & Yang, W. (2023) · npj Quantum Information · doi:10.1038/s41534-023-00760-2 · Cited by 15
Yamakami, T. (2021) · Information and Computation · doi:10.1016/j.ic.2021.104783 · Cited by 10
Chen, C.-Y. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02711-8 · Cited by 10
An optimal separation of randomized and Quantum query complexity
Sherstov, A. A., Storozhenko, A. A., & Wu, P. (2021) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3406325.3451019 · Cited by 17
Gender Recognition from Facial Images using Hybrid Classical-Quantum Neural Network
Mittal, S., & Dana, S. K. (2020) · Students Conference on Engineering and Systems · doi:10.1109/sces50439.2020.9236711 · Cited by 10
Hamiltonian complexity in the thermodynamic limit
Aharonov, D., & Irani, S. (2022) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3519935.3520067 · Cited by 10
Analytical error analysis of Clifford gates by the fault-path tracer method
Janardan, S., Tomita, Y., Gutiérrez, M., & Brown, K. R. (2016) · Quantum Information Processing · doi:10.1007/s11128-016-1330-z · Cited by 11
Ávila, A., Reiser, R., Pilla, M. L., & Yamin, A. (2016) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2016.7748342 · Cited by 10
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
