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 801–900 of 1,000
Yamakami, T. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-13435-8_10 · Cited by 4
Quantum algorithms for the Goldreich–Levin learning problem
Li, H. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02839-7 · Cited by 4
Resource Optimal Executable Quantum Circuit Generation Using Approximate Computing
Adarsh, S., & Möller, M. (2021) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce52317.2021.00040 · Cited by 4
Simple circuit simulations of classical and quantum Turing machines
Gurevich, Y. G., & Blass, A. R. (2022) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.2021.0891 · Cited by 4
Svozil, K. (2006) · Springer eBooks · doi:10.1007/3-211-37848-0_10 · Cited by 4
Noisy Random Quantum Circuit Sampling and its Classical Simulation
Zhang, M., Wang, C., & Han, Y. (2023) · Advanced Quantum Technologies · doi:10.1002/qute.202300030 · Cited by 4
Homomorphic encryption of the k=2 Bernstein–Vazirani algorithm
Fernández, P., & Martin-Delgado, M. A. (2024) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8121/ad6c04 · Cited by 4
Computing power of Turing machines in the framework of unsharp quantum logic
Shang, Y., Lu, X. P., & Lu, R. (2014) · Theoretical Computer Science · doi:10.1016/j.tcs.2014.12.015 · Cited by 4
Algorithms simulating natural phenomena and hypercomputation
Sharma, A. (2016) · IEEE Students Conference on Electrical, Electronics and Computer Science · doi:10.1109/sceecs.2016.7509337 · Cited by 4
On the Complexity of Finding the Maximum Entropy Compatible Quantum State
Giorgio, S. D., & Mateus, P. (2021) · RePEc: Research Papers in Economics · Cited by 4
ArsoNISQ: Analyzing Quantum Algorithms on Near-Term Architectures
Brandhofer, S., Devitt, S. J., & Polian, I. (2021) · IEEE European Test Symposium (ETS) · doi:10.1109/ets50041.2021.9465414 · Cited by 4
Automated Flag Qubit Insertion for Reliable Quantum Circuit Output
Acharya, N., & Saeed, S. M. (2021) · IEEE Computer Society Annual Symposium on VLSI · doi:10.1109/isvlsi51109.2021.00085 · Cited by 4
Mereghetti, C., & Palano, B. (2021) · ACM SIGACT News · doi:10.1145/3494656.3494666 · Cited by 4
Knot Theory, Jones Polynomial and Quantum Computing
Freivalds, R. (2005) · Lecture notes in computer science · doi:10.1007/11549345_2 · Cited by 4
Uniformity of quantum circuit families for error-free algorithms
Nishimura, H., & Ozawa, M. (2005) · Theoretical Computer Science · doi:10.1016/j.tcs.2004.12.020 · Cited by 4
Mathematical models of quantum computation
Nishino, T. (2002) · New Generation Computing · doi:10.1007/bf03037370 · Cited by 6
Schulman, L. J. (2005) · Nature · doi:10.1038/438431a · Cited by 4
Quantum Kolmogorov Complexity and Information-Disturbance Theorem
Miyadera, T. (2011) · Entropy · doi:10.3390/e13040778 · Cited by 4
Note on a universal quantum Turing machine
Iriyama, S., Miyadera, T., & Ohya, M. (2008) · Physics Letters A · doi:10.1016/j.physleta.2008.05.069 · Cited by 4
Generality’s price: Inescapable deficiencies in machine-learned programs
Case, J., Jain, S. K., Merkle, W., & Royer, J. S. (2006) · Cited by 4
QUANTUM-CLASSICAL CORRESPONDENCE IN THE ORACLE MODEL OF COMPUTATION
Wójcik, A., & Chhajlany, R. W. (2006) · International Journal of Quantum Information · doi:10.1142/s0219749906002109 · Cited by 4
Post-quantum Cryptography and a (Qu)Bit More
Maimuţ, D., & Simion, E. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-12942-2_3 · Cited by 4
A modeling and verification framework for optical quantum circuits
Beillahi, S. M., Mahmoud, M. Y., & Tahar, S. (2019) · Formal Aspects of Computing · doi:10.1007/s00165-019-00480-5 · Cited by 4
A Training Procedure for Quantum Random Vector Functional-link Networks
Panella, M., & Rosato, A. (2019) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2019.8683532 · Cited by 4
Digital Sources in Historiansʼ Research Practices: a Theoretical and Methodological Aspect
Sviatets, Y. (2020) · Universum Historiae et Archeologiae · doi:10.15421/26190105 · Cited by 4
A Quantum Polynomial Time Algorithm in Worst Case for Simon’s Problem
Mihara, T., & Sung, S. C. (1998) · Lecture notes in computer science · doi:10.1007/3-540-49381-6_25 · Cited by 4
Halting in quantum Turing computationPreprint
Fouché, W. L., Heidema, J., Jones, G., & Potgieter, P. H. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0705.3077 · Cited by 3
On generalized quantum turing machine and its language classes
Iriyama, S., & Ohya, M. (2007) · Cited by 4
Quantum algorithms for shifted subset problems
Montanaro, A. (2009) · Quantum Information and Computation · doi:10.26421/qic9.5-6-10 · Cited by 4
Quantum computation based on particle statisticsPreprint
Castagnoli, G., & Monti, D. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9806010 · Cited by 4
Simplified proof of the Fourier Sampling Theorem
Høyer, P. (2000) · Information Processing Letters · doi:10.1016/s0020-0190(00)00099-5 · Cited by 4
From classical versus quantum algorithms to P versus NPPreprint
Feldmann, M. (2012) · arXiv (Cornell University) · Cited by 4
Machines, Logic and Quantum PhysicsPreprint
Deutsch, D., EKERT, A. K., & Lupacchini, R. (1999) · arXiv (Cornell University) · doi:10.48550/arxiv.math/9911150 · Cited by 4
Intrinsically universal n-dimensional quantum cellular automataPreprint
Arrighi, P. J., & Grattage, J. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0907.3827 · Cited by 4
Dicke State Quantum Search for Solving the Vertex Cover Problem
Jiang, J. (2025) · Mathematics · doi:10.3390/math13183005 · Cited by 4
Parameterized Verification of Quantum Circuits
Abdulla, P. A., Chen, Y.-F., Hečko, M., Holík, L., Lengál, O., Lin, J.-A., & Thinniyam, R. S. (2026) · Proceedings of the ACM on Programming Languages · doi:10.1145/3776712 · Cited by 3
The Philosophy of Quantum Computing
Cuffaro, M. E. (2022) · Springer eBooks · doi:10.1007/978-3-030-95538-0_3 · Cited by 5
Quantum Algorithms for Compositional Text Processing
Laakkonen, T., Meichanetzidis, K., & Coecke, B. (2024) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.406.8 · Cited by 6
Hybrid classical-quantum image processing via polar Walsh basis functions
Rohida, M., Shukla, A., & Vedula, P. (2024) · Quantum Machine Intelligence · doi:10.1007/s42484-024-00205-9 · Cited by 3
Thirty years of quantum computing
Divincenzo, D. P. (2025) · Quantum Science and Technology · doi:10.1088/2058-9565/ade0e4 · Cited by 3
Quantum Algorithms for Intersection and Proximity Problems
Sadakane, K., Sugawara, N., & Tokuyama, T. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45678-3_14 · Cited by 3
The Polynomial Degree of Recursive Fourier Sampling
Johnson, B. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-18073-6_9 · Cited by 3
Undecidable, Unrecognizable, and Quantum Computing
Siomau, M. (2020) · Quantum Reports · doi:10.3390/quantum2030023 · Cited by 3
Building a quantum computer (invited)
Sanders, B. C. (2020) · doi:10.1145/3414622.3431913 · Cited by 3
A Review on Quantum Computing Approach for Next-Generation Energy Storage Solution
Khalid, A., Tufail, S., & Sarwat, A. I. (2021) · IEEE SoutheastCon · doi:10.1109/southeastcon45413.2021.9401854 · Cited by 3
Nagata, K., & Nakamura, T. (2021) · International Journal of Theoretical Physics · doi:10.1007/s10773-021-04894-x · Cited by 3
Artificial Intelligence in Medicine Using Quantum Computing in the Future of Healthcare
Davids, J., Lidströmer, N., & Ashrafian, H. (2021) · Springer eBooks · doi:10.1007/978-3-030-58080-3_338-1 · Cited by 4
Orchestrating Measurement-Based Quantum Computation over Photonic Quantum Processors
Li, Y., Pawar, A., Azari, M., Guo, Y., Zhang, Y., Yang, J., Seshadreesan, K. P., & Tang, X. (2023) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1109/dac56929.2023.10247944 · Cited by 5
Quixote: Improving Fidelity of Quantum Program by Independent Execution of Controlled Gates
Jang, E., Choi, S., & Ro, W. W. (2023) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1109/dac56929.2023.10247757 · Cited by 3
Mathematical digital quantum computation by means of much more logical skills
Nagata, K., & Nakamura, T. (2024) · Quantum Studies Mathematics and Foundations · doi:10.1007/s40509-024-00326-7 · Cited by 3
Quantum advantage in temporally flat measurement-based quantum computation
de Oliveira, M., Barbosa, L. S., & Galvão, E. F. (2024) · Quantum · doi:10.22331/q-2024-04-09-1312 · Cited by 5
Improving Probabilistic Error Cancellation in the Presence of Nonstationary Noise
Dasgupta, S., & Humble, T. S. (2024) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2024.3435757 · Cited by 3
Robust Fitting on a Gate Quantum Computer
Yang, F. F., Sasdelli, M., & Chin, T.-J. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-73232-4_7 · Cited by 4
Modeling and Simulating Rydberg Atom Quantum Computers for Hardware-Software Co-design with PachinQo
Ludmir, J., Huo, Y., DiBrita, N. S., & Patel, T. (2024) · Proceedings of the ACM on Measurement and Analysis of Computing Systems · doi:10.1145/3700421 · Cited by 3
ASDF: A Compiler for Qwerty, a Basis-Oriented Quantum Programming Language
Adams, A. J., Khan, S., Bhamra, A. S., Abusaada, R. R., Cabrera, A. M., Hoechst, C. C., Humble, T. S., Young, J., & Conte, T. M. (2025) · Proceedings of the CGO/Proceedings of the ... CGO · doi:10.1145/3696443.3708966 · Cited by 3
Quantum Kolmogorov complexity and bounded quantum memory
Miyadera, T. (2011) · Physical Review A · doi:10.1103/physreva.83.042316 · Cited by 3
Robust Cache-Aware Quantum Processor Layout
LeCompte, T., Qi, F., & Peng, L. (2020) · IEEE Symposium on Reliable Distributed Systems (SRDS) · doi:10.1109/srds51746.2020.00035 · Cited by 3
Machine learning assisted quantum adiabatic algorithm design
Lin, J. H., Ye, M., Zhu, J., & Li, X. (2021) · Acta Physica Sinica · doi:10.7498/aps.70.20210831 · Cited by 3
Can a Quantum Computer Run the von Neumann Architecture?
Hines, P. (2010) · Lecture notes in physics · doi:10.1007/978-3-642-12821-9_14 · Cited by 3
An improved architecture of a realizable quantum computer for quantum programming languages
Wu, N., Song, F., & Li, X. (2009) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.823463 · Cited by 3
Turing machines based on unsharp quantum logic
Shang, Y., Lu, X. P., & Lu, R. (2012) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.95.17 · Cited by 3
Quantum Iterative Deepening with an Application to the Halting Problem
Tarrataca, L. D. T. J., & Wichert, A. (2013) · PLoS ONE · doi:10.1371/journal.pone.0057309 · Cited by 4
Study on Quantum Parallel Processing by Adiabatic Quantum Computation in Bernstein-Vazirani Problem
Nakayama, S., Gang, P., & Iimura, I. (2012) · International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT) · doi:10.1109/pdcat.2012.140 · Cited by 3
Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding
Kawachi, A., & Yamakami, T. (2010) · SIAM Journal on Computing · doi:10.1137/080716840 · Cited by 3
ON THE QUANTUM KOLMOGOROV COMPLEXITY OF CLASSICAL STRINGS
Müller, M. P. (2009) · International Journal of Quantum Information · doi:10.1142/s0219749909005456 · Cited by 3
How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?
Ambainis, A., & de Wolf, R. (2013) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2013.26 · Cited by 3
On a method of solving SAT efficiently using the quantum Turing machine
Mihara, T., & Nishino, T. (2002) · Workshop on Physics and Computation (PhysComp) · doi:10.1109/phycmp.1994.363683 · Cited by 3
Orthogonal Vector Computations
Svozil, K. (2016) · Entropy · doi:10.3390/e18050156 · Cited by 3
Quantum cryptographic property testing of multi-output Boolean functions
Jingyi, C., & Guo, J. (2019) · Quantum Information Processing · doi:10.1007/s11128-019-2299-1 · Cited by 3
Lineal: A linear-algebraic Lambda-calculus
Arrighi, P. J., & Gilles Dowek, B. (2006) · HAL · doi:10.48550/arxiv.quant-ph/0612199 · Cited by 3
Fundamental Physics and Computation: The Computer-Theoretic Framework
Miguel-Tomé, S., Lázaro, Á. L. S., & Alonso-Romero, L. (2022) · Universe · doi:10.3390/universe8010040 · Cited by 3
A Review on Applications of Quantum Computing in Machine Learning
Paul, S., & Mitra, A. (2022) · Advances in systems analysis, software engineering, and high performance computing book series · doi:10.4018/978-1-7998-9183-3.ch005 · Cited by 3
Quantum adiabatic algorithms using unitary interpolation*
Zhang, S., Duan, Q.-H., Li, T., Fu, X.-Q., Huang, H.-L., Wang, X., & Bao, W. (2019) · Chinese Physics B · doi:10.1088/1674-1056/ab5f02 · Cited by 3
A local model of quantum Turing machines
Wang, D. (2020) · Quantum Information and Computation · doi:10.26421/qic20.3-4-3 · Cited by 4
Quantum and Classical Complexity Classes: Separations, Collapses, and Closure Properties
Spakowski, H., Thakur, M., & Tripathi, R. S. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-24597-1_32 · Cited by 2
Implementation of quantum algorithms with Josephson charge qubits
Schuch, N. (2002) · University of Regensburg Publication Server (University of Regensburg) · doi:10.5283/epub.1511 · Cited by 5
Universal Sets of Quantum Information Processing Primitives and Their Optimal Use
Gruska, J. (2006) · Lecture notes in computer science · doi:10.1007/11889342_24 · Cited by 3
On Perfect Completeness for QMAPreprint
Aaronson, S. (2008) · arXiv (Cornell University) · Cited by 4
Gate-based Quantum Computing: An OverviewPreprint
da Silva, R. P. (2023) · SSRN Electronic Journal · doi:10.2139/ssrn.4347584 · Cited by 4
Demonstration of measurement-free universal logical quantum computation
Butt, F., Pogorelov, I., Freund, R., Steiner, A., Meyer, M., Monz, T., & Müller, M. (2026) · Nature Communications · doi:10.1038/s41467-026-68533-x · Cited by 2
Abdelmoumin, G., Liu, C., & Rawat, D. B. (2023) · International Conference on Computational Science and Computational Intelligence (CSCI) · doi:10.1109/csci62032.2023.00073 · Cited by 2
Disentangling the Gap Between Quantum and #SAT
Mei, J., Martens, J., & Laarman, A. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-77019-7_2 · Cited by 3
PIMutation: Exploring the Potential of Real PIM Architecture for Quantum Circuit Simulation
Lee, D. T., Jang, E., Choi, S., An, J., Kim, C., & Ro, W. W. (2025) · Asia and South Pacific Design Automation Conference (ASP-DAC) · doi:10.1145/3658617.3697583 · Cited by 2
Trade-offs in Cryptosystems by Boolean and Quantum Circuits
Lavagna, L., Falco, F. D., Ceschini, A., Rosato, A., & Panella, M. (2025) · IEEE International Symposium on Circuits and Systems proceedings · doi:10.1109/iscas56072.2025.11043205 · Cited by 2
Productive Quantum Programming Needs Better Abstract Machines
Núñez-Corrales, S., Matteo, O. D., Dumbell, J., Edwards, M., Giusto, E., Pakin, S., & Stirbu, V. (2025) · IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce65121.2025.00094 · Cited by 2
Quo Vadis, Quantum Machine Learning?: Quantum kernel methods meet Earth observation
Miroszewski, A., Nalepa, J., Wijata, A. M., B, J. M. A., Saux, B. L., & Sebastianelli, A. (2026) · IEEE Geoscience and Remote Sensing Magazine · doi:10.1109/mgrs.2025.3596291 · Cited by 2
Fiber Optics Protocols for Quantum Communication
Massar, S. (2006) · Quantum Information Processing · doi:10.1007/s11128-006-0029-y · Cited by 2
Using Reed-Muller Expansions in the Synthesis and Optimization of Boolean Quantum Circuits
Younes, A. (2017) · Emergence, complexity and computation · doi:10.1007/978-3-319-67997-6_5 · Cited by 2
Efficient Quantum Algorithm for the Parity Problem of a Certain Function
Nagata, K., Nakamura, T., Batle, J. A. I., & Farouk, A. (2018) · International Journal of Theoretical Physics · doi:10.1007/s10773-018-3827-y · Cited by 2
Quantum Algorithm for Determining a Complex Number String
Nagata, K., Geurdes, H. J. F., Patro, S. K., Heidari, S., Farouk, A., & Nakamura, T. (2019) · International Journal of Theoretical Physics · doi:10.1007/s10773-019-04239-9 · Cited by 2
Quantum Algorithms and Methods
Djordjević, I. B. (2021) · Elsevier eBooks · doi:10.1016/b978-0-12-821982-9.00006-x · Cited by 2
Schuld, M., & Petruccione, F. (2021) · Quantum science and technology · doi:10.1007/978-3-030-83098-4_9 · Cited by 2
Schuld, M., & Petruccione, F. (2018) · Quantum science and technology · doi:10.1007/978-3-319-96424-9_4 · Cited by 2
Educational Issues Raised by the Availability of the Quantum Computer
Koczka, F., Prantner, C. K., & Bíró, C. (2023) · Central-European Journal of New Technologies in Research Education and Practice · doi:10.36427/cejntrep.5.1.5051 · Cited by 2
VelociTI: An Architecture-level Performance Modeling Framework for Trapped Ion Quantum Computers
Hankin, A., Mahmoud, A., Hempstead, M., Brooks, D. M., & Wei, G.-Y. (2023) · IEEE International Symposium on Workload Characterization · doi:10.1109/iiswc59245.2023.00040 · Cited by 2
Use Cases of Quantum Networks for Industry and Science
Pande, M. B. (2023) · International Conference on Computing Communication Control and automation · doi:10.1109/iccubea58933.2023.10392063 · Cited by 2
Kunde, V., Nold, J. M., & Hielscher, J. (2024) · European Symposium on Usable Security (EuroUSEC) · doi:10.1145/3688459.3688468 · Cited by 2
Sarode, K. (2024) · IEEE International Conference on High Performance Computing, Data, and Analytics · doi:10.1109/hipc62374.2024.00026 · Cited by 2
A quantum approach for optimal control
Sandesara, H., Shukla, A., & Vedula, P. (2025) · Quantum Information Processing · doi:10.1007/s11128-025-04710-z · Cited by 2
S-SYNC: Shuttle and Swap Co-Optimization in Quantum Charge-Coupled Devices
Zhu, C., Wu, X. G., Wang, J., & Wang, X. (2025) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1145/3695053.3731084 · Cited by 9
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
