Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.03705

Unitary complexity in polynomial space

William Kretschmer, Ewin Tang

quant-phcs.CCcs.CRSubmitted Oct 2, 2026• Announced Oct 5, 2026• 2 citations• Revised Oct 5, 2026 (v2)
v1 · Oct 2, 2026v2 · Oct 5, 2026
arXivHTMLPDF

Abstract

We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or $\mathsf{BPP} \neq \mathsf{NEXP}$. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. We prove our main result as a consequence of a more general lemma, which shows that every unitary in $\mathsf{unitaryPSPACE}$ either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for $\mathsf{NEXP}$ search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving $\mathsf{unitaryPSPACE}$ would imply breakthrough classical lower bounds such as $\mathsf{NC} \neq \mathsf{NP}$. Along the way, we propose new definitions for the unitary complexity classes $\mathsf{unitaryP}$ and $\mathsf{unitaryPSPACE}$. Our changes address the biggest conceptual issues with definitions suggested in prior work, and lead to elegant proofs. We study both implementations that erase garbage and implementations that allow it, because we cannot rule out the possibility that the two definitions differ. Nevertheless, we show that both definitions can be viewed as special cases of each other. We also showcase many other ways in which our definitions are robust. For example, we show that $\mathsf{unitaryPSPACE}$ has an equivalent characterization as the set of unitary transformations whose entries can be computed to arbitrary precision in polynomial space. Consequently, we deduce that $\mathsf{unitaryPSPACE}$ can generically erase garbage, a result that provably fails relative to unitary oracles.

AI Summary

The paper asks how space-bounded unitary computation relates to classical computational hardness, and whether quantum commitments imply conventional complexity separations. It also revisits definitions of unitary complexity to address composition and precision issues. Its central lemma states that every $\mathcal U\in\mathsf{unitaryPSPACE}$ either cannot be implemented in polynomial time relative to any classical oracle, or can be implemented with an oracle returning bits of valid $\mathsf{NEXP}$ witnesses. Consequently, quantum commitments imply either that polynomial-time unitary synthesis is impossible or that $\mathsf{BPP}\ne\mathsf{NEXP}$. Certain classical-oracle separations between unitary complexity classes similarly imply either failure of efficient synthesis or the unrelativized separation $\mathsf{NC}\ne\mathsf{NP}$. The definitions require uniform time or space polynomial in $n$ and $\log(1/\varepsilon)$, distinguishing clean implementations from implementations leaving input-independent garbage. A characterization identifies $\mathsf{unitaryPSPACE}$ with unitary families whose entries are approximable in polynomial space. Its proof combines entry estimation, state synthesis, and conversion of column constructors into unitary implementations. The central lemma then uses exponential-size oracle truth tables as witnesses, verified by simulating circuits and comparing their entries with the target unitary. Polynomial-space implementations can erase garbage after choosing a global phase; clean and garbage-allowing classes are also related through constructions such as $U\otimes U^\dagger$. Garbage erasure fails relative to suitable unitary oracles, while its polynomial-time, unrelativized version remains open. Neither efficient unitary synthesis nor any stated classical separation is resolved unconditionally; the cryptographic consequence is a disjunction.

Likely largely AI-generatedAI use disclosed
The authors verified all of the AI-generated proofs and reworked them for clarity.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
42 pages. v2: minor corrections

Related papers

unitaryQIP = unitaryPSPACE

Entong He, Fengning Ou, Mingnan Zhao

Unitary synthesis complexity studies the computational cost of applying a target unitary to an unknown quantum state, extending complexity theory beyond its traditional focus on problems with classical inputs and outputs. Rosenthal and Yuen (ITCS 2022) introduced two complexity classes for unitary synthesis: $\mathsf{unitaryQIP}$ and $\mathsf{unitaryPSPACE}$ for the unitary families implementable via interactive proofs and in polynomial space, respectively. In this work, we prove the equality $\mathsf{unitaryQIP}=\mathsf{unitaryPSPACE}$ and thereby establish a unitary-complexity analogue of $\mathsf{QIP} = \mathsf{PSPACE}$ (Jain, Ji, Upadhyay, and Watrous, J. ACM 2011) and $\mathsf{stateQIP}=\mathsf{statePSPACE}$ (Rosenthal and Yuen, ITCS 2022; Metger and Yuen, FOCS 2023). To prove $\mathsf{unitaryQIP} \subseteq \mathsf{unitaryPSPACE}$, we use an acceptance rigidity lemma derived from the soundness condition to show that the polynomial-space prover constructed for a fixed input in state synthesis (Metger and Yuen, FOCS 2023) implements the target unitary on every input, leading to a polynomial-space simulation of the protocol. For the reverse inclusion, we build on OpenAI's recently announced solution to the unitary synthesis problem (Aaronson and Kuperberg, Theory Comput. 2007), and show that $\mathsf{unitaryPSPACE}$ families can be synthesized in polynomial time with a $\mathsf{PSPACE}$ oracle. We then implement the oracle queries using auxiliary states prepared via the $\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}$ protocol (Rosenthal and Yuen, ITCS 2022). Beyond the equality, we show that our protocol for $\mathsf{unitaryPSPACE}$ can be parallelized to constant rounds when the verifier receives polynomially many copies of the input, and we also obtain a complexity-theoretic barrier to proving the existence of $\mathsf{EFI}$ pairs.

quant-pharXiv:2611.02819•Nov 3, 2026•0 citations

Explicit Separations for One-Query Unitary Synthesis

Fangqi Dong, Alex Lombardi, Fermi Ma

The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every $n$-qubit unitary $U$ is computable by efficient quantum circuits relative to some classical oracle $f = f_U$ depending on $U$. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly$(n)$ parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries $P\lvert x\rangle = \lvert π(x)\rangle$, as well as random alternating-basis phase unitaries $F_2 \cdot H^{\otimes n} \cdot F_1$. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries $\lvert x\rangle\mapsto α_x \lvert x\rangle$, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.

quant-pharXiv:2607.26478•Jul 30, 2026•3 citations

State Synthesis with an NP oracle

Aniruddha Sen

In this note, I describe a quantum algorithm that prepares an arbitrary state $|ψ\rangle$ to inverse exponential precision in polynomial time by making queries to an $\mathsf{NP}$ oracle, assuming one can directly query entries of the state vector corresponding to $|ψ\rangle$. The previous best upper bound on the complexity class required by an oracle for this task was $\mathsf{PP}$. I provide evidence that $\mathsf{NP}$ is the best possible upper bound by showing that any quantum algorithm using a $\mathsf{P}$ oracle, or even a $\mathsf{P/poly}$ oracle, requires exponentially many queries. I also discuss some implications of this result for the $\mathsf{QMA}$ search-to-decision problem and unitary synthesis.

quant-pharXiv:2611.02370•Nov 3, 2026•0 citations

A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography

Alex Lombardi, Fermi Ma, John Wright

The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any n-qubit unitary U can be implemented by an efficient quantum algorithm A augmented with an oracle that computes an arbitrary Boolean function f. In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function? In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries U such that no quantum polynomial-time oracle algorithm Af can implement U, even approximately, if it only makes one (quantum) query to f. Our approach also has implications for quantum cryptography: we prove (relative to a random oracle) the existence of quantum cryptographic primitives that remain secure against all one-query adversaries Af. Since such one-query algorithms can decide any language, solve any classical search problem, and even prepare any quantum state, our result suggests that implementing random unitaries and breaking quantum cryptography may be harder than all of these tasks. To prove this result, we formulate unitary synthesis as an efficient challenger-adversary game, which enables proving lower bounds by analyzing the maximum success probability of an adversary Af. Our main technical insight is to identify a natural spectral relaxation of the one-query optimization problem, which we bound using tools from random matrix theory. We view our framework as a potential avenue to rule out polynomial-query unitary synthesis, and we state conjectures in this direction.

arXiv:2310.08870•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•40 citations

Quantum Search-To-Decision Reductions and the State Synthesis Problem

Sandy Irani, Anand Natarajan, Chinmay Nirkhe +2 more

It is a useful fact in classical computer science that many search problems are reducible to decision problems; this has led to decision problems being regarded as the $\textit{de facto}$ computational task to study in complexity theory. In this work, we explore search-to-decision reductions for quantum search problems, wherein a quantum algorithm makes queries to a classical decision oracle to output a desired quantum state. In particular, we focus on search-to-decision reductions for $\mathsf{QMA}$, and show that there exists a quantum polynomial-time algorithm that can generate a witness for a $\mathsf{QMA}$ problem up to inverse polynomial precision by making one query to a $\mathsf{PP}$ decision oracle. We complement this result by showing that $\mathsf{QMA}$-search does $\textit{not}$ reduce to $\mathsf{QMA}$-decision in polynomial-time, relative to a quantum oracle. We also explore the more general $\textit{state synthesis problem}$, in which the goal is to efficiently synthesize a target state by making queries to a classical oracle encoding the state. We prove that there exists a classical oracle with which any quantum state can be synthesized to inverse polynomial precision using only one oracle query and to inverse exponential precision using two oracle queries. This answers an open question of Aaronson from 2016, who presented a state synthesis algorithm that makes $O(n)$ queries to a classical oracle to prepare an $n$-qubit state, and asked if the query complexity could be made sublinear.

arXiv:2111.02999•Leibniz international proceedings in informatics•Nov 4, 2021•31 citations

Quantum Complexity Theory

Ethan Bernstein, Umesh V. Vazirani

In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient 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 specified. We prove that $O(\log T)$ bits of precision suffice to support a T step computation. This justifies 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 first 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 efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. 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.

SIAM Journal on Computing•Oct 1, 1997•1,635 citations
We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or BPP≠NEXP\mathsf{BPP} \neq \mathsf{NEXP}BPP=NEXP. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. We prove our main result as a consequence of a more general lemma, which shows that every unitary in unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for NEXP\mathsf{NEXP}NEXP search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE would imply breakthrough classical lower bounds such as NC≠NP\mathsf{NC} \neq \mathsf{NP}NC=NP.
Along the way, we propose new definitions for the unitary complexity classes unitaryP\mathsf{unitaryP}unitaryP and unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE. Our changes address the biggest conceptual issues with definitions suggested in prior work, and lead to elegant proofs. We study both implementations that erase garbage and implementations that allow it, because we cannot rule out the possibility that the two definitions differ. Nevertheless, we show that both definitions can be viewed as special cases of each other. We also showcase many other ways in which our definitions are robust. For example, we show that unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE has an equivalent characterization as the set of unitary transformations whose entries can be computed to arbitrary precision in polynomial space. Consequently, we deduce that unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE can generically erase garbage, a result that provably fails relative to unitary oracles.
The paper asks how space-bounded unitary computation relates to classical computational hardness, and whether quantum commitments imply conventional complexity separations. It also revisits definitions of unitary complexity to address composition and precision issues.
Its central lemma states that every U∈unitaryPSPACE\mathcal U\in\mathsf{unitaryPSPACE}U∈unitaryPSPACE either cannot be implemented in polynomial time relative to any classical oracle, or can be implemented with an oracle returning bits of valid NEXP\mathsf{NEXP}NEXP witnesses. Consequently, quantum commitments imply either that polynomial-time unitary synthesis is impossible or that BPP≠NEXP\mathsf{BPP}\ne\mathsf{NEXP}BPP=NEXP. Certain classical-oracle separations between unitary complexity classes similarly imply either failure of efficient synthesis or the unrelativized separation NC≠NP\mathsf{NC}\ne\mathsf{NP}NC=NP.
The definitions require uniform time or space polynomial in nnn and log⁡(1/ε)\log(1/\varepsilon)log(1/ε), distinguishing clean implementations from implementations leaving input-independent garbage. A characterization identifies unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE with unitary families whose entries are approximable in polynomial space. Its proof combines entry estimation, state synthesis, and conversion of column constructors into unitary implementations. The central lemma then uses exponential-size oracle truth tables as witnesses, verified by simulating circuits and comparing their entries with the target unitary.
Polynomial-space implementations can erase garbage after choosing a global phase; clean and garbage-allowing classes are also related through constructions such as U⊗U†U\otimes U^\daggerU⊗U†. Garbage erasure fails relative to suitable unitary oracles, while its polynomial-time, unrelativized version remains open. Neither efficient unitary synthesis nor any stated classical separation is resolved unconditionally; the cryptographic consequence is a disjunction.
Unitary synthesis complexity studies the computational cost of applying a target unitary to an unknown quantum state, extending complexity theory beyond its traditional focus on problems with classical inputs and outputs. Rosenthal and Yuen (ITCS 2022) introduced two complexity classes for unitary synthesis: unitaryQIP\mathsf{unitaryQIP}unitaryQIP and unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE for the unitary families implementable via interactive proofs and in polynomial space, respectively. In this work, we prove the equality unitaryQIP=unitaryPSPACE\mathsf{unitaryQIP}=\mathsf{unitaryPSPACE}unitaryQIP=unitaryPSPACE and thereby establish a unitary-complexity analogue of QIP=PSPACE\mathsf{QIP} = \mathsf{PSPACE}QIP=PSPACE (Jain, Ji, Upadhyay, and Watrous, J. ACM 2011) and stateQIP=statePSPACE\mathsf{stateQIP}=\mathsf{statePSPACE}stateQIP=statePSPACE (Rosenthal and Yuen, ITCS 2022; Metger and Yuen, FOCS 2023). To prove unitaryQIP⊆unitaryPSPACE\mathsf{unitaryQIP} \subseteq \mathsf{unitaryPSPACE}unitaryQIP⊆unitaryPSPACE, we use an acceptance rigidity lemma derived from the soundness condition to show that the polynomial-space prover constructed for a fixed input in state synthesis (Metger and Yuen, FOCS 2023) implements the target unitary on every input, leading to a polynomial-space simulation of the protocol. For the reverse inclusion, we build on OpenAI's recently announced solution to the unitary synthesis problem (Aaronson and Kuperberg, Theory Comput. 2007), and show that unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE families can be synthesized in polynomial time with a PSPACE\mathsf{PSPACE}PSPACE oracle. We then implement the oracle queries using auxiliary states prepared via the statePSPACE⊆stateQIP\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}statePSPACE⊆stateQIP protocol (Rosenthal and Yuen, ITCS 2022). Beyond the equality, we show that our protocol for unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE can be parallelized to constant rounds when the verifier receives polynomially many copies of the input, and we also obtain a complexity-theoretic barrier to proving the existence of EFI\mathsf{EFI}EFI pairs.
The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every nnn-qubit unitary UUU is computable by efficient quantum circuits relative to some classical oracle f=fUf = f_Uf=fU​ depending on UUU. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly(n)(n)(n) parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries P∣x⟩=∣π(x)⟩P\lvert x\rangle = \lvert π(x)\rangleP∣x⟩=∣π(x)⟩, as well as random alternating-basis phase unitaries F2⋅H⊗n⋅F1F_2 \cdot H^{\otimes n} \cdot F_1F2​⋅H⊗n⋅F1​. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries ∣x⟩↦αx∣x⟩\lvert x\rangle\mapsto α_x \lvert x\rangle∣x⟩↦αx​∣x⟩, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.
In this note, I describe a quantum algorithm that prepares an arbitrary state ∣ψ⟩|ψ\rangle∣ψ⟩ to inverse exponential precision in polynomial time by making queries to an NP\mathsf{NP}NP oracle, assuming one can directly query entries of the state vector corresponding to ∣ψ⟩|ψ\rangle∣ψ⟩. The previous best upper bound on the complexity class required by an oracle for this task was PP\mathsf{PP}PP. I provide evidence that NP\mathsf{NP}NP is the best possible upper bound by showing that any quantum algorithm using a P\mathsf{P}P oracle, or even a P/poly\mathsf{P/poly}P/poly oracle, requires exponentially many queries. I also discuss some implications of this result for the QMA\mathsf{QMA}QMA search-to-decision problem and unitary synthesis.
The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any n-qubit unitary U can be implemented by an efficient quantum algorithm A augmented with an oracle that computes an arbitrary Boolean function f. In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function? In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries U such that no quantum polynomial-time oracle algorithm Af can implement U, even approximately, if it only makes one (quantum) query to f. Our approach also has implications for quantum cryptography: we prove (relative to a random oracle) the existence of quantum cryptographic primitives that remain secure against all one-query adversaries Af. Since such one-query algorithms can decide any language, solve any classical search problem, and even prepare any quantum state, our result suggests that implementing random unitaries and breaking quantum cryptography may be harder than all of these tasks. To prove this result, we formulate unitary synthesis as an efficient challenger-adversary game, which enables proving lower bounds by analyzing the maximum success probability of an adversary Af. Our main technical insight is to identify a natural spectral relaxation of the one-query optimization problem, which we bound using tools from random matrix theory. We view our framework as a potential avenue to rule out polynomial-query unitary synthesis, and we state conjectures in this direction.
It is a useful fact in classical computer science that many search problems are reducible to decision problems; this has led to decision problems being regarded as the de facto\textit{de facto}de facto computational task to study in complexity theory. In this work, we explore search-to-decision reductions for quantum search problems, wherein a quantum algorithm makes queries to a classical decision oracle to output a desired quantum state. In particular, we focus on search-to-decision reductions for QMA\mathsf{QMA}QMA, and show that there exists a quantum polynomial-time algorithm that can generate a witness for a QMA\mathsf{QMA}QMA problem up to inverse polynomial precision by making one query to a PP\mathsf{PP}PP decision oracle. We complement this result by showing that QMA\mathsf{QMA}QMA-search does not\textit{not}not reduce to QMA\mathsf{QMA}QMA-decision in polynomial-time, relative to a quantum oracle. We also explore the more general state synthesis problem\textit{state synthesis problem}state synthesis problem, in which the goal is to efficiently synthesize a target state by making queries to a classical oracle encoding the state. We prove that there exists a classical oracle with which any quantum state can be synthesized to inverse polynomial precision using only one oracle query and to inverse exponential precision using two oracle queries. This answers an open question of Aaronson from 2016, who presented a state synthesis algorithm that makes O(n)O(n)O(n) queries to a classical oracle to prepare an nnn-qubit state, and asked if the query complexity could be made sublinear.
In this paper we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient 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 specified. We prove that O(log⁡T)O(\log T)O(logT) bits of precision suffice to support a T step computation. This justifies 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 first 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 efficiently decidable (with small error-probability) on a quantum Turing machine satisfies $\BPP \subseteq \BQP \subseteq \Ptime^{\SP}$. 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.