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 701–800 of 1,000
Linear-algebraic lambda-calculusPreprint
Arrighi, P. J., & Gilles Dowek, B. (2005) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0501150 · Cited by 7
Erratum: 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_73 · Cited by 7
A Hybrid Quantum Search Engine: A Fast Quantum Algorithm for Multiple MatchesPreprint
Younes, A., Rowe, J., & Miller, J. F. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0311171 · Cited by 8
Quantum-Resistant Security: PQC Readiness and Research Challenges (Invited)
Kundu, A., & Kompella, R. R. (2025) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1109/dac63849.2025.11132566 · Cited by 6
New Method of Calculating a Multiplication by using the Generalized Bernstein-Vazirani Algorithm
Nagata, K., Nakamura, T., Geurdes, H. J. F., Batle, J. A. I., Abdalla, S., & Farouk, A. (2018) · International Journal of Theoretical Physics · doi:10.1007/s10773-018-3687-5 · Cited by 6
Quantum Differential Meet‐In‐The‐Middle Attack and Some Applications to Lightweight Ciphers
Xu, Y., Cai, B., Yuan, Z., Qin, S., Gao, F., & Wen, Q. (2024) · Advanced Quantum Technologies · doi:10.1002/qute.202400157 · Cited by 6
A Survey on the Quantum Security of Block Cipher-Based Cryptography
Bootsma, S. E., & Vries, M. D. (2024) · IEEE Access · doi:10.1109/access.2024.3520364 · Cited by 6
A Generalization of the Bernstein-Vazirani Algorithm
Nagata, K. (2017) · MOJ Ecology & Environmental Sciences · doi:10.15406/mojes.2017.02.00010 · Cited by 6
A high-performance compilation strategy for multiplexing quantum control architecture
Shan, Z., Zhu, Y., & Zhao, B. (2022) · Scientific Reports · doi:10.1038/s41598-022-11154-3 · Cited by 7
Q2Logic: A Coarse-Grained FPGA Overlay targeting Schrödinger Quantum Circuit Simulations
Podobas, A. (2023) · IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum · doi:10.1109/ipdpsw59300.2023.00078 · Cited by 6
Rosmanis, A. (2011) · Physical Review A · doi:10.1103/physreva.83.022304 · Cited by 9
Lin, T. (2012) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2012.01.004 · Cited by 6
Veiled Nonlocality and Quantum Darwinism
Kak, S. C. (2015) · NeuroQuantology · doi:10.14704/nq.2015.13.1.803 · Cited by 5
Quantum algorithm for SAT problem andquantum mutual entropy
Ohya, M. (2005) · Reports on Mathematical Physics · doi:10.1016/s0034-4877(05)80007-2 · Cited by 6
Interactive environment for implementation and simulation of quantum algorithms
Raychev, N., & Racheva, E. (2015) · International Conference on Computer Systems and Technologies (CompSysTech) · doi:10.1145/2812428.2812456 · Cited by 6
Sharma, N., Rawat, T. K., Parthasarathy, H., & Gautam, K. (2016) · Quantum Information Processing · doi:10.1007/s11128-016-1270-7 · Cited by 6
The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling
Remscrim, Z. (2016) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2016.29 · Cited by 6
Y-Calculus: A Language for Real Matrices Derived from the ZX-Calculus
Jeandel, E., Perdrix, S., & Vilmart, R. (2018) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.266.2 · Cited by 6
Improving direct state measurements by using rebits in real enlarged Hilbert spaces
Ho, L. B. (2018) · Physics Letters A · doi:10.1016/j.physleta.2018.10.047 · Cited by 6
Classifying quantum data by dissipation
Marshall, J., Venuti, L. C., & Paolo Zanardi, A. (2019) · Physical Review A · doi:10.1103/physreva.99.032330 · Cited by 6
Reliability testing, noise and error correction of real quantum computing devices
Galanis, I., Savvas, I. Κ., Chernov, A. V., & Butakova, M. A. (2021) · Telfor Journal · doi:10.5937/telfor2101041g · Cited by 6
The non-adaptive query complexity of testing k-parities
Buhrman, H., García-Soriano, D., Matsliah, A., & de Wolf, R. (2013) · Chicago Journal of Theoretical Computer Science · doi:10.4086/cjtcs.2013.006 · Cited by 6
Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound
Belovs, A. (2014) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2014.11 · Cited by 6
Hayes, B. (1995) · Cited by 6
Higher-order perturbation theory for decoherence in Grover’s algorithm
Azuma, H. (2005) · Physical Review A · doi:10.1103/physreva.72.042305 · Cited by 8
Quantum Principles and Mathematical Computability
Kieu, T. D. (2005) · International Journal of Theoretical Physics · doi:10.1007/s10773-005-7070-y · Cited by 6
Kumar, M., Boshra-riad, S., Nachimuthu, Y., & Perkowski, M. A. (2010) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2010.5586003 · Cited by 6
Upper bounds on the noise threshold for fault-tolerant quantum computing
Kempe, J., Regev, O., Unger, F., & de Wolf, R. (2010) · Quantum Information and Computation · doi:10.26421/qic10.5-6-1 · Cited by 6
General Bounds for Quantum Biased Oracles
Iwama, K., Raymond, R., & Yamashita, S. (2005) · IPSJ Digital Courier · doi:10.2197/ipsjdc.1.415 · Cited by 6
Quantum Algorithms for Continuous Problems and Their Applications
Papageorgiou, A., & Traub, J. F. (2014) · Advances in chemical physics · doi:10.1002/9781118742631.ch06 · Cited by 6
Models of Quantum Computers and Decoherence ProblemPreprint
Volovich, I. V. (1999) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9902055 · Cited by 6
Quantum Computing and Shor`s Factoring AlgorithmPreprint
Volovich, I. V. (2001) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0109004 · Cited by 8
On the approximability of the energy function of Ising spin glasses
Bertoni, A., Campadelli, P., & Molteni, G. (1994) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/27/20/012 · Cited by 6
Computability Theory of Closed Timelike CurvesPreprint
Aaronson, S., Bavarian, M., Cubitt, T. S., Grewal, S., Gueltrini, G., O’Donnell, R., & Raat, M. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1609.05507 · Cited by 6
Mukhopadhyay, P. (2021) · Journal of Physics Communications · doi:10.1088/2399-6528/ac3a43 · Cited by 6
Pedagogical Approach for Quantum Computing in Engineering Education
Orts, F. J. (2025) · Computer Applications in Engineering Education · doi:10.1002/cae.70004 · Cited by 5
A Review on Models and Applications of Quantum Computing
Grigoryan, E., Kumar, S., & Pinheiro, P. R. (2025) · Quantum Reports · doi:10.3390/quantum7030039 · Cited by 10
Moderate exponential-time quantum dynamic programming across the subsets for scheduling problems
Grange, C., Poss, M., Bourreau, E., t'Kindt, V., & Ploton, O. (2024) · European Journal of Operational Research · doi:10.1016/j.ejor.2024.09.005 · Cited by 5
A Logic for Quantum Circuits and Protocols
Patra, M. K. (2005) · Lecture notes in computer science · doi:10.1007/11560647_28 · Cited by 5
Quantum learning Boolean linear functions w.r.t. product distributions
Caro, M. C. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02661-1 · Cited by 5
Towards Out-of-Core Simulators for Quantum Computing
Trummer, I. (2024) · Workshop on Quantum Computing and Quantum-Inspired Technology for Data-Intensive Systems and Applications (Q-Data) · doi:10.1145/3665225.3665441 · Cited by 5
Survey on Computational Applications of Tensor-Network Simulations
García, M. D., & Romero, A. M. (2024) · IEEE Access · doi:10.1109/access.2024.3519676 · Cited by 13
Quantum Hidden Subgroup Algorithms: An Algorithmic Toolkit
Lomonaco, S. J., & Kauffman, L. H. (2007) · Chapman & Hall/CRC eBooks · doi:10.1201/9781584889007-7 · Cited by 5
Performance simulator based on hardware resources constraints for ion trap quantum computer
Ahsan, M., Choi, B.-S., & Kim, J. (2013) · IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD) · doi:10.1109/iccd.2013.6657073 · Cited by 5
Computing with quanta—impacts of quantum theory on computation
Hirvensalo, M. (2002) · Theoretical Computer Science · doi:10.1016/s0304-3975(02)00096-8 · Cited by 5
Introduction to the World of Quantum Computers
Jafarpour, S. (2006) · IEEE International Conference on Cognitive Informatics · doi:10.1109/coginf.2006.365585 · Cited by 5
Fourier Transforms and Quantum Computation
Vazirani, U. V. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45878-6_8 · Cited by 5
Self-citationAutoQP: Genetic Programming for Quantum Programming
Ahsan, U., & Minhas, F. (2020) · International Bhurban Conference on Applied Sciences and Technology (IBCAST) · doi:10.1109/ibcast47879.2020.9044554 · Cited by 5
QDLC - THE QUANTUM DEVELOPMENT LIFE CYCLE
Dey, N., Ghosh, M., Chakrabarti, A., & Saha, R. (2026) · doi:10.34218/ijqc_04_01_002 · Cited by 5
An Exact Quantum Algorithm for the 2-Junta Problem
Chen, C.-Y. (2021) · International Journal of Theoretical Physics · doi:10.1007/s10773-020-04662-3 · Cited by 5
An exact quantum algorithm for testing 3-junta in Boolean functions with one uncomplemented product
Chen, C.-Y. (2021) · Quantum Information Processing · doi:10.1007/s11128-020-02953-6 · Cited by 5
Prefix-free quantum Kolmogorov complexity
Bhojraj, T. (2021) · Theoretical Computer Science · doi:10.1016/j.tcs.2021.05.017 · Cited by 5
Towards Compact Modeling of Noisy Quantum Computers: A Molecular-Spin-Qubit Case of Study
Cignoni, M., Cirillo, G. A., Turvani, G., Graziano, M., & Zamboni, M. (2021) · ACM Journal on Emerging Technologies in Computing Systems · doi:10.1145/3474223 · Cited by 5
NISQ-friendly measurement-based quantum clustering algorithms
Patil, S., Banerjee, S., & Panigrahi, P. K. (2024) · Quantum Information Processing · doi:10.1007/s11128-024-04553-0 · Cited by 5
Testing the shift-equivalence of polynomials using quantum machines
Grigoriev, D. Y. (1996) · Journal of Mathematical Sciences · doi:10.1007/bf02362466 · Cited by 5
Multiple Entities Search through Simon's Quantum Algorithm
Sihare, S. R., & Nath, V. V. (2017) · IEEE International Advance Computing Conference · doi:10.1109/iacc.2017.0162 · Cited by 5
Yan, S. Y. (2018) · Springer eBooks · doi:10.1007/978-3-319-72536-9_5 · Cited by 6
Chapter 4 A Status Report on the P Versus NP Question
Allender, E. (2009) · Advances in computers · doi:10.1016/s0065-2458(09)01204-2 · Cited by 5
Postselection Finite Quantum Automata
Scegulnaja-Dubrovska, O., Lāce, L., & Freivalds, R. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13523-1_14 · Cited by 5
Universality and programmability of quantum computers
Fouché, W. L., Heidema, J., Jones, G., & Potgieter, P. H. (2008) · Theoretical Computer Science · doi:10.1016/j.tcs.2008.05.007 · Cited by 5
Andrecut, M., & Ali, M. (2004) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/37/34/l01 · Cited by 5
Partial Observation of Quantum Turing Machines and a Weaker Well-Formedness Condition
Perdrix, S. (2011) · Electronic Notes in Theoretical Computer Science · doi:10.1016/j.entcs.2011.01.009 · Cited by 5
Role of interference and entanglement in quantum neural processing
Ezhov, A. A., & Berman, G. P. (2001) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.449168 · Cited by 6
On the Impossibility of Interaction-Free Quantum Sensing for Small I/O Bandwidth
Reif, J. H. (2000) · Information and Computation · doi:10.1006/inco.2000.2880 · Cited by 5
Quantum Formulas: A Lower Bound and Simulation
Roychowdhury, V., & Vatan, F. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539700370965 · Cited by 7
On beating the hybrid argument
Fefferman, B., Shaltiel, R., Umans, C., & Viola, E. (2012) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2090236.2090273 · Cited by 5
Can Arbitrary Quantum Systems Undergo Self-replication?
Pati, A. K., & Braunstein, S. L. (2008) · IMPERIAL COLLEGE PRESS eBooks · doi:10.1142/9781848162556_0011 · Cited by 5
Quantum simulations of classical random walks and undirected graph connectivity
Watrous, J. (2003) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.1999.766275 · Cited by 5
SINGLE-STEP QUANTUM SEARCH USING PROBLEM STRUCTURE
Hogg, T. (2000) · International Journal of Modern Physics C · doi:10.1142/s0129183100000663 · Cited by 6
Quantum Computation: From the Sequential Approach to Simulated Annealing
Castagnoli, G., EKERT, A. K., & Macchiavello, C. (1998) · International Journal of Theoretical Physics · doi:10.1023/a:1026612111666 · Cited by 6
Quantum lower bounds for the Goldreich–Levin problem
Adcock, M., Cleve, R., Iwama, K., Putra, R., & Yamashita, S. (2006) · Information Processing Letters · doi:10.1016/j.ipl.2005.01.016 · Cited by 4
Fault-tolerant quantum computer architectures using hierarchies of quantum error-correcting codes
Chuang, I. L., & Cross, A. W. (2008) · Cited by 7
Quantum Computational Number Theory
Yan, S. Y. (2012) · Wiley eBooks · doi:10.1002/9781118188606.ch10 · Cited by 5
Cellular Automata as a Model of Physical SystemsPreprint
Cheung, D., & Pérez-Delgado, C. A. (2008) · Kent Academic Repository (University of Kent) · doi:10.48550/arxiv.0809.1790 · Cited by 5
Local Search Methods for Quantum ComputersPreprint
Hogg, T., & Yanik, M. F. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9802043 · Cited by 5
Quantum Smart MatterPreprint
Hogg, T., & Chase, J. G. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9611021 · Cited by 5
Tensor norms and the classical communication complexity of nonlocal quantum measurement
Shi, Y. (2005) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1060590.1060659 · Cited by 5
Azuma, H. (2002) · Physical Review A · doi:10.1103/physreva.66.019903 · Cited by 6
A Generalization of Bernstein-Vazirani Algorithm to Qudit SystemsPreprint
Krishna, R. N., Makwana, V., & Suresh, A. P. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1609.03185 · Cited by 5
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 · Cited by 5
Efficient Algorithms for Universal Quantum SimulationPreprint
Sanders, B. C. (2016) · Cited by 5
Open and Closed Loop Approaches for Energy Efficient Quantum Optimal Control
Fauquenot, S., Sarkar, A., & Feld, S. (2025) · Advanced Quantum Technologies · doi:10.1002/qute.202400690 · Cited by 4
Controlled formalized operators
Raychev, N. (2015) · International Journal of Scientific and Engineering Research · doi:10.14299/ijser.2015.05.003 · Cited by 4
Quantum Algorithms and Oracles with the Scalable ZX-calculus
Carette, T., D'Anello, Y., & Perdrix, S. (2021) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.343.10 · Cited by 4
Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
Zhang, Z., & Ying, M. (2025) · Proceedings of the ACM on Programming Languages · doi:10.1145/3729283 · Cited by 12
Recovering the Original Simplicity: Succinct and Exact Quantum Algorithm for the Welded Tree Problem
Li, G., Li, L., & Luo, J. (2024) · Algorithmica · doi:10.1007/s00453-024-01273-w · Cited by 5
Fast algorithms for classical specifications of stabiliser states and Clifford gates
de Silva, N., Salmon, W., & Yin, M. (2025) · Quantum · doi:10.22331/q-2025-01-08-1586 · Cited by 10
Peter Shor on the genesis of Shor’s algorithm
Zierler, D., & Dahn, R. (2025) · Physics Today · doi:10.1063/pt.ifad.hcak · Cited by 4
ArtA: automating Design Space Exploration of spin-qubit architectures
Paraskevopoulos, N., Hamel, D., Sarkar, A., Almudéver, C. G., & Feld, S. (2025) · Quantum Information Processing · doi:10.1007/s11128-025-04759-w · Cited by 4
Quantum enhanced stratification of breast cancer: exploring quantum expressivity for real omics data
Repetto, V., Ceroni, E. G., Buonaiuto, G., & D’Aurizio, R. (2025) · Quantum Machine Intelligence · doi:10.1007/s42484-025-00289-x · Cited by 15
Quantum Counterfeit Coin Problems
Iwama, K., Nishimura, H., Raymond, R., & Teruyama, J. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17517-6_10 · Cited by 4
Zhang, Z., Chen, G., Diao, Z., & Hemmer, P. (2009) · Advances in mechanics and mathematics · doi:10.1007/978-0-387-75714-8_14 · Cited by 4
Approximation of fuzzy context-free grammars
Wang, Y., & Li, Y. (2009) · Information Sciences · doi:10.1016/j.ins.2009.06.028 · Cited by 4
On the Completeness of Quantum Computation Models
Arrighi, P. J., & Gilles Dowek, B. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13962-8_3 · Cited by 4
Representation-theoretical properties of the approximate quantum Fourier transform
Rötteler, M., & Beth, T. (2008) · Applicable Algebra in Engineering Communication and Computing · doi:10.1007/s00200-008-0072-2 · Cited by 4
Tarrataca, L., & Wichert, A. (2011) · Quantum Information Processing · doi:10.1007/s11128-011-0241-2 · Cited by 4
Kochen-Specker Theorem as a Precondition for Quantum Computing
Nagata, K., & Nakamura, T. (2016) · International Journal of Theoretical Physics · doi:10.1007/s10773-016-3140-6 · Cited by 4
Ahlswede, R. (2016) · Foundations in signal processing, communications and networking · doi:10.1007/978-3-319-31515-7_4 · Cited by 4
A milestone in quantum computing
Bartlett, S. D. (2016) · Nature · doi:10.1038/536035a · Cited by 4
Observation of photonic states dynamics in 3-D integrated Fourier circuits
Flamini, F., Viggianiello, N., Giordani, T., Bentivegna, M., Spagnolo, N., Crespi, A., Corrielli, G., Osellame, R., Martin-Delgado, M. A., & Sciarrino, F. (2018) · Journal of Optics · doi:10.1088/2040-8986/aac68b · Cited by 4
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
