CoChat
Sign Up
Cited by 1,284Quantum Computing Algorithms and ArchitectureComputability, Logic, AI AlgorithmsComplexity and Algorithms in Graphs

Quantum complexity theory

Bernstein, Ethan, Vazirani, Umesh·1993·Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93
DOI 10.1145/167088.167097
Open this paper in CoChat — free account

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.

Integrity signals

Registry

Crossref · 10.1145/167088.167097

Cites

37 of 37 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

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?

  • 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.

    “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]

  • Given any QTM M and any set Σ', there is a QTM M' such that M' behaves exactly as M while leaving its second track unchanged.

    “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]

  • If M1 and M2 are well-behaved, normal form QTMs with the same alphabet, then there is a normal form QTM M which carries out the computation of M1 followed by the computation of M2.

    “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]

  • 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.

    “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]

  • Given any QTM M and permutation π, there is a QTM M' such that M' behaves exactly as M except that its tracks are permuted according to π.

    “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]

Cites

Flagged first, then by citations

1 of the 38 references couldn’t be matched to a known paper.

Cited by

Sorted by citations

Related

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
DOI
10.1145/167088.167097
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
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
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