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 301–400 of 1,000
VERITAS: Accurately Estimating the Correct Output on Noisy Intermediate-Scale Quantum Computers
Patel, T., & Tiwari, D. (2020) · International Conference for High Performance Computing, Networking, Storage and Analysis (SC) · doi:10.1109/sc41405.2020.00019 · Cited by 36
Systematic Approaches for Precise and Approximate Quantum State Runtime Assertion
Liu, J., & Zhou, H. (2021) · IEEE International Symposium on High-Performance Computer Architecture (HPCA) · doi:10.1109/hpca51647.2021.00025 · Cited by 41
Quantum tomography using state-preparation unitaries
van Apeldoorn, J., Cornelissen, A., Gilyén, A., & Nannicini, G. (2023) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611977554.ch47 · Cited by 34
Bio‐Inspired and Nanoscale Integrated Computing
Eshaghian‐Wilner, M. M., & service), W. I. (. (2009) · Wiley eBooks · doi:10.1002/9780470429983 · Cited by 34
Models of quantum computation and quantum programming languages
Miszczak, J. A. (2011) · Bulletin of the Polish Academy of Sciences Technical Sciences · doi:10.2478/v10175-011-0039-5 · Cited by 38
Sharp Quantum versus Classical Query Complexity Separations
de Beaudrap, N., Available, N. A. N., & Available, N. A. N. (2002) · Algorithmica · doi:10.1007/s00453-002-0978-1 · Cited by 34
A Foundation of Programming a Multi-tape Quantum Turing Machine
Yamakami, T. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48340-3_39 · Cited by 34
Remarks on universal quantum computer
Shi, Y. (2002) · Physics Letters A · doi:10.1016/s0375-9601(02)00015-4 · Cited by 33
Automata and quantum computing
Ambainis, A., & Yakaryılmaz, A. (2021) · EMS Press eBooks · doi:10.4171/automata-2/17 · Cited by 33
Error-bounded probabilistic computations between MA and AM
Böhler, E., Glaßer, C., & Meister, D. (2006) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2006.05.001 · Cited by 33
Spin qubits for quantum simulations
Peng, X., & Suter, D. (2009) · 物理学前沿：英文版 · doi:10.1007/s11467-009-0067-x · Cited by 33
Yamakami, T., & Yao, A. C.-C. (1999) · Information Processing Letters · doi:10.1016/s0020-0190(99)00084-8 · Cited by 35
Kieu, T. D. (2002) · Minds and Machines · doi:10.1023/a:1021130831101 · Cited by 33
Quantum computing classical physics
Meyer, D. (2002) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.2001.0936 · Cited by 34
Quantum Computing: Lecture NotesPreprint
de Wolf, R. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1907.09415 · Cited by 197
Quantum lower bound for recursive Fourier sampling
Aaronson, S. (2003) · Quantum Information and Computation · doi:10.26421/qic3.2-7 · Cited by 38
Golovkins, M. (2000) · Lecture notes in computer science · doi:10.1007/3-540-44411-4_22 · Cited by 32
Hypercomputation with quantum adiabatic processes
Kieu, T. D. (2004) · Theoretical Computer Science · doi:10.1016/j.tcs.2003.12.006 · Cited by 32
Determination of equivalence between quantum sequential machines
Li, L., & Qiu, D. (2006) · Theoretical Computer Science · doi:10.1016/j.tcs.2006.03.001 · Cited by 31
Cosmological lower bound on the circuit complexity of a small problem in logic
Stockmeyer, L. J., & Meyer, A. R. (2002) · Journal of the ACM · doi:10.1145/602220.602223 · Cited by 32
Various Aspects of Finite Quantum Automata
Hirvensalo, M. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-85780-8_2 · Cited by 31
A quantum algorithm for approximating the influences of Boolean functions and its applications
Li, H., & Yang, L. (2015) · Quantum Information Processing · doi:10.1007/s11128-015-0954-8 · Cited by 31
Tetrapartite entanglement features of W-Class state in uniform acceleration
Dong, Q., Torres-Arenas, A. J., Sun, G.-H., & Dong, S. (2019) · Frontiers of Physics · doi:10.1007/s11467-019-0940-1 · Cited by 31
Exploiting Long-Distance Interactions and Tolerating Atom Loss in Neutral Atom Quantum Architectures
Baker, J. M., Litteken, A., Duckering, C., Hoffmann, H., Bernien, H., & Chong, F. T. (2021) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca52012.2021.00069 · Cited by 42
Diagonal quantum circuits: Their computational power and applications
Nakata, Y., & Murao, M. (2014) · The European Physical Journal Plus · doi:10.1140/epjp/i2014-14152-9 · Cited by 33
The geometry of quantum learning
Hunziker, M., Meyer, D., Park, J., Pommersheim, J., & Rothstein, M. J. (2009) · Quantum Information Processing · doi:10.1007/s11128-009-0129-6 · Cited by 35
Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
Müller, M. P. (2008) · IEEE Transactions on Information Theory · doi:10.1109/tit.2007.913263 · Cited by 31
Topological quantum computing and the Jones polynomial
Lomonaco, S. J., & Kauffman, L. H. (2006) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.665361 · Cited by 33
Lower bounds for quantum communication complexity
Klauck, H. (2001) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959903 · Cited by 33
Accelerated quantum Monte Carlo with probabilistic computers
Chowdhury, S., Camsari, K. Y., & Datta, S. (2023) · Communications Physics · doi:10.1038/s42005-023-01202-3 · Cited by 35
On quantum lambda calculi: a foundational perspective
Zorzi, M. (2014) · Mathematical Structures in Computer Science · doi:10.1017/s0960129514000425 · Cited by 33
Optimization and experimental realization of the quantum permutation algorithm
Yalçınkaya, İ., & Gedik, Z. (2017) · Physical Review A · doi:10.1103/physreva.96.062339 · Cited by 29
First experiences of teaching quantum computing
Carrascal, G., Barrio, A. A. D., & Botella, G. (2020) · The Journal of Supercomputing · doi:10.1007/s11227-020-03376-x · Cited by 30
Bit-Slicing the Hilbert Space: Scaling Up Accurate Quantum Circuit Simulation
Tsai, Y.-H., Jiang, J.-H. R., & Jhang, C.-S. (2021) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1109/dac18074.2021.9586191 · Cited by 30
Bounds on the Power of Constant-Depth Quantum Circuits
Fenner, S., Green, F., Homer, S. T., & Zhang, Y. (2005) · Lecture notes in computer science · doi:10.1007/11537311_5 · Cited by 30
On perfect completeness for QMA
Aaronson, S. (2009) · Quantum Information and Computation · doi:10.26421/qic9.1-2-5 · Cited by 44
Hierarchy and equivalence of multi-letter quantum finite automata
Qiu, D., & Yü, S. (2009) · Theoretical Computer Science · doi:10.1016/j.tcs.2009.03.040 · Cited by 28
Quantum Algorithmic Complexities and Entropy
Benatti, F. (2009) · Open Systems & Information Dynamics · doi:10.1142/s1230161209000025 · Cited by 30
Quantum versus classical learnability
Servedio, R. A., & Gortler, S. J. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2001.933881 · Cited by 38
Languages Recognized with Unbounded Error by Quantum Finite Automata
Yakaryılmaz, A., & Say, A. C. C. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03351-3_33 · Cited by 30
Quantum Computing and Phase Transitions in Combinatorial Search
Hogg, T. (1996) · Journal of Artificial Intelligence Research · doi:10.1613/jair.204 · Cited by 29
A probabilistic model of computing with words
Qiu, D., & Wang, H. (2004) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2004.08.006 · Cited by 30
A fast quantum mechanical algorithm for estimating the medianPreprint
Grover, L. K. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9607024 · Cited by 30
Formal constraint-based compilation for noisy intermediate-scale quantum systems
Murali, P., Javadi-Abhari, A., Chong, F. T., & Martonosi, M. (2019) · Microprocessors and Microsystems · doi:10.1016/j.micpro.2019.02.005 · Cited by 29
Approximate Equivalence Checking of Noisy Quantum Circuits
Hong, X., Ying, M., Feng, Y., Zhou, X., & Li, S. (2021) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1109/dac18074.2021.9586214 · Cited by 34
Quantum software engineering and quantum software development lifecycle: a survey
Dwivedi, K., Haghparast, M., & Mikkonen, T. (2024) · Cluster Computing · doi:10.1007/s10586-024-04362-1 · Cited by 36
Mitra, A., Ghosh, A., Das, R., Patel, A. D., & Kumar, A. (2005) · Journal of Magnetic Resonance · doi:10.1016/j.jmr.2005.08.004 · Cited by 28
Efficient classical simulation of the Deutsch–Jozsa and Simon’s algorithms
Johansson, N., & Larsson, J.-Å. (2017) · Quantum Information Processing · doi:10.1007/s11128-017-1679-7 · Cited by 29
The Complexity of Translationally Invariant Spin Chains with Low Local Dimension
Bausch, J., Cubitt, T. S., & Ozols, M. (2017) · UCL Discovery (University College London) · doi:10.17863/cam.15638 · Cited by 29
The Multiplicative Quantum Adversary
Špalek, R. (2008) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2008.9 · Cited by 42
Quantum Search Algorithm with more Reliable Behaviour using Partial Diffusion
Younes, A. (2004) · AIP conference proceedings · doi:10.1063/1.1834408 · Cited by 29
AutoQ: An Automata-Based Quantum Circuit Verifier
Chen, Y., Chung, K.-M., Lengál, O., Lin, J.-A., & Tsai, W.-L. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-37709-9_7 · Cited by 28
An efficient quantum algorithm for preparation of uniform quantum superposition states
Shukla, A., & Vedula, P. (2024) · Quantum Information Processing · doi:10.1007/s11128-024-04258-4 · Cited by 44
Ding, Y., & Chong, F. T. (2020) · Synthesis lectures on computer architecture · doi:10.2200/s01014ed1v01y202005cac051 · Cited by 63
Adiabatic Quantum Graph Matching with Permutation Matrix Constraints
Benkner, M. S., Golyanik, V., Theobalt, C., & Moeller, M. (2020) · International Conference on 3D Vision (3DV) · doi:10.1109/3dv50981.2020.00068 · Cited by 28
QCB: Efficient Quantum-Secure Authenticated Encryption
Bhaumik, R., Bonnetain, X., Chailloux, A., Leurent, G., Naya‐Plasencia, M., Schrottenloher, A., & Seurin, Y. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-92062-3_23 · Cited by 29
An Efficient Exact Quantum Algorithm for the Integer Square-free Decomposition Problem
Li, J., Peng, X., Du, J., & Suter, D. (2012) · Scientific Reports · doi:10.1038/srep00260 · Cited by 29
Quantum circuits and low-degree polynomials over F 2
Montanaro, A. (2017) · Journal of Physics A Mathematical and Theoretical · doi:10.1088/1751-8121/aa565f · Cited by 34
Quantum Search on Structured Problems
Grover, L. K. (1999) · Chaos Solitons & Fractals · doi:10.1016/s0960-0779(98)00217-3 · Cited by 28
Quantum advantage without entanglement
Kenigsberg, D., Mor, A., & Ratsaby, G. (2006) · Quantum Information and Computation · doi:10.26421/qic6.7-4 · Cited by 27
Local Convertibility and the Quantum Simulation of Edge States in Many-Body Systems
Franchini, F., Cui, J., Luigi Amico, A., Fan, H., Gu, M., Korepin, V. E., Kwek, L. C., & Vedral, V. (2014) · Physical Review X · doi:10.1103/physrevx.4.041028 · Cited by 29
Dominant Strategies of Quantum Games on Quantum Periodic Automata
Giannakis, K., Papalitsas, C., Kastampolidou, K., Singh, A., & Andronikos, T. (2015) · Computation · doi:10.3390/computation3040586 · Cited by 27
An investigation of IBM quantum computing device performance on combinatorial optimisation problems
Khumalo, M. T., Chieza, H. A., Prag, K., & Woolway, M. (2022) · Neural Computing and Applications · doi:10.1007/s00521-022-07438-4 · Cited by 38
Single-qubit universal classifier implemented on an ion-trap quantum device
Dutta, T., Pérez-Salinas, A., Cheng, J. P. S., Latorre, J. I., & Mukherjee, M. (2022) · Physical Review A · doi:10.1103/physreva.106.012411 · Cited by 34
Decoherence in Grover’s quantum algorithm: Perturbative approach
Azuma, H. (2002) · Physical Review A · doi:10.1103/physreva.65.042311 · Cited by 27
On Halting Process of Quantum Turing Machine
Miyadera, T., & Ohya, M. (2005) · Open Systems & Information Dynamics · doi:10.1007/s11080-005-0923-2 · Cited by 27
On communication over an entanglement-assisted quantum channel
Nayak, A., & Salzman, J. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.510007 · Cited by 27
A quantum jump in computer science
Brassard, G. (1995) · Lecture notes in computer science · doi:10.1007/bfb0015233 · Cited by 28
Nishimura, H., & Ozawa, M. (2005) · Cited by 27
Selected Topics in Simulated Annealing
Aarts, E., & Korst, J. (2002) · Operations research, computer science. Interface series · doi:10.1007/978-1-4615-1507-4_1 · Cited by 26
Period finding with adiabatic quantum computation
Hen, I. (2014) · Europhysics Letters (EPL) · doi:10.1209/0295-5075/105/50005 · Cited by 29
A Quantum Computational Approach to Correspondence Problems on Point Sets
Golyanik, V., & Theobalt, C. (2020) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr42600.2020.00920 · Cited by 26
Yamakami, T. (1999) · Lecture notes in computer science · doi:10.1007/3-540-46691-6_33 · Cited by 24
The stabilisation of quantum computations
Berthiaume, A., Deutsch, D., & Jozsa, R. (2002) · Workshop on Physics and Computation (PhysComp) · doi:10.1109/phycmp.1994.363698 · Cited by 25
Towards quantum computing based community detection
Akbar, S., & Saritha, S. K. (2020) · Computer Science Review · doi:10.1016/j.cosrev.2020.100313 · Cited by 26
Orchestrated trios: compiling for efficient communication in Quantum programs with 3-Qubit gates
Duckering, C., Baker, J. M., Litteken, A., & Chong, F. T. (2021) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/3445814.3446718 · Cited by 27
Verifiable Quantum Advantage without Structure
Yamakawa, T., & Zhandry, M. (2024) · Journal of the ACM · doi:10.1145/3658665 · Cited by 58
Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound
Belovs, A. (2015) · Computational Complexity · doi:10.1007/s00037-015-0099-2 · Cited by 25
High Level Structures for Quantum Computing
Miszczak, J. A. (2012) · Synthesis lectures on quantum computing · doi:10.1007/978-3-031-02516-7 · Cited by 26
On Beating the Hybrid Argument
Fefferman, B., Shaltiel, R., Umans, C., & Viola, E. (2013) · Theory of Computing · doi:10.4086/toc.2013.v009a026 · Cited by 25
On Exact Quantum Query Complexity
Montanaro, A., Jozsa, R., Mitchison, G., et al. (2011) · Cited by 25
Bound on the number of functions that can be distinguished with k quantum queries
Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (1999) · Physical Review A · doi:10.1103/physreva.60.4331 · Cited by 32
Self-testing of universal and fault-tolerant sets of quantum gates
van Dam, W., Magniez, F., Mosca, M., & Sántha, M. (2000) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/335305.335402 · Cited by 26
Exponential lower bound for 2-query locally decodable codes via a quantum argument
Kerenidis, I., & de Wolf, R. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780559.780560 · Cited by 25
Measurement-Based Quantum Turing Machines and Questions of UniversalitiesPreprint
Perdrix, S., & Jorrand, P. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0404146 · Cited by 32
A Rosetta stone for quantum mechanics with an introduction to quantum computation
Lomonaco, S. J. (2010) · Proceedings of symposia in applied mathematics · doi:10.1090/psapm/068/2762150 · Cited by 26
Time to reinspect the foundations?
Copeland, J., Dresner, E., Proudfoot, D., & Shagrir, O. (2016) · Communications of the ACM · doi:10.1145/2908733 · Cited by 24
Quantum information cannot be split into complementary parts
Zhou, D., Zeng, B., & You, L. (2005) · Physics Letters A · doi:10.1016/j.physleta.2005.11.041 · Cited by 24
Quantum Private Information Retrieval with Sublinear Communication Complexity
Gall, F. L. (2012) · Theory of Computing · doi:10.4086/toc.2012.v008a016 · Cited by 24
Classical and Quantum Complexity of the Sturm–Liouville Eigenvalue Problem
Papageorgiou, A., & Woźniakowski, H. (2005) · Quantum Information Processing · doi:10.1007/s11128-005-4481-x · Cited by 26
Three approaches to the quantitative definition of information in an individual pure quantum state
Vitanyi, P. M. B. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2000.856757 · Cited by 24
Using HDLs for describing quantum circuits
Udrescu, M., Prodan, L., & Vlăduţiu, M. (2004) · ACM International Conference on Computing Frontiers (CF) · doi:10.1145/977091.977107 · Cited by 24
Rooß, D., & Wagner, K. W. (1996) · Information and Computation · doi:10.1006/inco.1996.0094 · Cited by 24
Quantum algorithmic information theoryPreprint
Svozil, K. (1995) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9510005 · Cited by 24
A quantum algorithm to approximate the linear structures of Boolean functions
Li, H., & Yang, L. (2016) · Mathematical Structures in Computer Science · doi:10.1017/s0960129516000013 · Cited by 27
TILT: Achieving Higher Fidelity on a Trapped-Ion Linear-Tape Quantum Computing Architecture
Wu, X.-C., Debroy, D. M., Ding, Y., Baker, J. M., Alexeev, Y., Brown, K. R., & Chong, F. T. (2021) · IEEE International Symposium on High-Performance Computer Architecture (HPCA) · doi:10.1109/hpca51647.2021.00023 · Cited by 33
Performance Evaluation and Acceleration of the QTensor Quantum Circuit Simulator on GPUs
Lykov, D., Chen, A., Chen, H., Keipert, K., Zhang, Z., Gibbs, T., & Alexeev, Y. (2021) · IEEE/ACM International Workshop on Quantum Computing Software (QCS) · doi:10.1109/qcs54837.2021.00007 · Cited by 23
Distributed exact Grover’s algorithm
Zhou, X., Qiu, D., & Luo, L. (2023) · Frontiers of Physics · doi:10.1007/s11467-023-1327-x · Cited by 24
Quantum computation with coherent spin states and the close Hadamard problem
Adcock, M. R. A., Høyer, P., & Sanders, B. C. (2016) · Quantum Information Processing · doi:10.1007/s11128-015-1229-0 · Cited by 24
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
