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:2404.04198

A no-go result for pure state synthesis in the DQC1 model

Zachary Stier

Published Apr 5, 2024• 1 citation
arXivHTMLPDF

Abstract

We study the problem of state synthesis in the DQC1 (One Clean Qubit) model of quantum computation, which provides a single pure qubit and $n$ maximally mixed qubits, and after applying any quantum circuit some subset of the qubits are measured or discarded. In the case of discarding, we show that it is impossible to prepare additional pure qubits, and that it is impossible to prepare very low-temperature Gibbs states on additional qubits. In the case of measurements, we show that the probability of synthesizing $m$ additional qubits is bounded by $2^{1-m}$, and that the probability of preparing low-temperature Gibbs states is bounded by $2^{2-m}$. As a consequence, we give a lower-bound the runtime of a recently studied class of repeated interaction quantum algorithms. The techniques used study states and circuits at the level of entries of their respective density and unitary matrices.

DOI
10.48550/arxiv.2404.04198

Related papers

Hardness of Classically Simulating the One-Clean-Qubit Model

Tomoyuki Morimae, Keisuke Fujii, Joseph F. Fitzsimons

Deterministic quantum computation with one quantum bit (DQC1) [E. Knill and R. Laflamme, Phys. Rev. Lett. 81, 5672 (1998)] is a model of quantum computing where the input is restricted to containing a single qubit in a pure state and has all other qubits in a completely mixed state. Only the single pure qubit is measured at the end of the computation. While it is known that DQC1 can efficiently solve several problems for which no known classical efficient algorithms exist, the question of whether DQC1 is really more powerful than classical computation remains open. In this Letter, we introduce a slightly modified version of DQC1, which we call DQC1(k), where k output qubits are measured, and show that DQC1(k) cannot be classically efficiently simulated for any k≥3 unless the polynomial hierarchy collapses at the third level.

arXiv:1312.2496•Physical Review Letters•Apr 2, 2014•108 citations

Classical simulatability of the one clean qubit model

Tomoyuki Morimae, Takeshi Koshiba

Deterministic quantum computation with one quantum bit (DQC1), or the one clean qubit model, [E. Knill and R. Laflamme, Phys. Rev. Lett. {\bf81}, 5672 (1998)] is a model of quantum computing where the input is the tensor product of a single pure qubit and many completely-mixed states, and only the single qubit is measured at the end of the computation. In spite of its naive appearance, the DQC1 model can efficiently solve some problems for which no classical efficient algorithms are known, and therefore it has been conjectured that the DQC1 model is more powerful than classical computing (under the assumption of $\mbox{BPP}\subsetneq\mbox{BQP}$). Here we show that the output probability distribution of the DQC1 model cannot be classically efficiently approximated (exactly within a polynomial bit length or in the fully polynomial randomized approximation scheme (FPRAS) with at most a constant error) unless $\mbox{BQP}\subseteq\mbox{BPP}$.

arXiv:1405.6840•May 27, 2014•2 citations

Computational synthesis of any n -qubit pure or mixed state

Song Lin, Colin P. Williams

Future quantum information processing devices will require the use of exotic quantum states, such as specially crafted entangled states, to achieve certain desired computations on demand. Thus far, synthesis schemes for such states have been devised on a case-by-case basis using ad hoc techniques. In this paper we present a systematic method for finding a quantum circuit that can synthesize any pure or mixed n-qubit state. We then give examples of the use of our algorithm for finding synthesis pathways for especially exotic quantum states such as maximal mixed states. It is not known how to prepare general instances of such states by other means. Thus our quantum state synthesis algorithm should be of use not only in quantum information processing, but also in experimental quantum physics.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 5, 2003•5 citations

Power of one nonclean qubit

Tomoyuki Morimae, Keisuke Fujii, Harumichi Nishimura

The one-clean qubit model (or the DQC1 model) is a restricted model of quantum computing where only a single qubit of the initial state is pure and others are maximally mixed. Although the model is not universal, it can efficiently solve several problems whose classical efficient solutions are not known. Furthermore, it was recently shown that if the one-clean qubit model is classically efficiently simulated, the polynomial hierarchy collapses to the second level. A disadvantage of the one-clean qubit model is, however, that the clean qubit is too clean: for example, in realistic NMR experiments, polarizations are not high enough to have the perfectly pure qubit. In this paper, we consider a more realistic one-clean qubit model, where the clean qubit is not clean, but depolarized. We first show that, for any polarization, a multiplicative-error calculation of the output probability distribution of the model is possible in a classical polynomial time if we take an appropriately large multiplicative error. The result is in strong contrast with that of the ideal one-clean qubit model where the classical efficient multiplicative-error calculation (or even the sampling) with the same amount of error causes the collapse of the polynomial hierarchy. We next show that, for any polarization lower-bounded by an inverse polynomial, a classical efficient sampling (in terms of a sufficiently small multiplicative error or an exponentially small additive error) of the output probability distribution of the model is impossible unless BQP (bounded error quantum polynomial time) is contained in the second level of the polynomial hierarchy, which suggests the hardness of the classical efficient simulation of the one nonclean qubit model.

arXiv:1610.07244•Physical Review A•Apr 25, 2017•18 citations

Impossibility of Classically Simulating One-Clean-Qubit Model with Multiplicative Error

Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae +3 more

The one-clean-qubit model (or the deterministic quantum computation with one quantum bit model) is a restricted model of quantum computing where all but a single input qubits are maximally mixed. It is known that the probability distribution of measurement results on three output qubits of the one-clean-qubit model cannot be classically efficiently sampled within a constant multiplicative error unless the polynomial-time hierarchy collapses to the third level [T. Morimae, K. Fujii, and J. F. Fitzsimons, Phys. Rev. Lett. 112, 130502 (2014)PRLTAO0031-900710.1103/PhysRevLett.112.130502]. It was open whether we can keep the no-go result while reducing the number of output qubits from three to one. Here, we solve the open problem affirmatively. We also show that the third-level collapse of the polynomial-time hierarchy can be strengthened to the second-level one. The strengthening of the collapse level from the third to the second also holds for other subuniversal models such as the instantaneous quantum polynomial model [M. Bremner, R. Jozsa, and D. J. Shepherd, Proc. R. Soc. A 467, 459 (2011)PRLAAZ1364-502110.1098/rspa.2010.0301] and the boson sampling model [S. Aaronson and A. Arkhipov, STOC 2011, p. 333]. We additionally study the classical simulatability of the one-clean-qubit model with further restrictions on the circuit depth or the gate types.

arXiv:1409.6777•Physical Review Letters•May 17, 2018•67 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
We study the problem of state synthesis in the DQC1 (One Clean Qubit) model of quantum computation, which provides a single pure qubit and nnn maximally mixed qubits, and after applying any quantum circuit some subset of the qubits are measured or discarded. In the case of discarding, we show that it is impossible to prepare additional pure qubits, and that it is impossible to prepare very low-temperature Gibbs states on additional qubits. In the case of measurements, we show that the probability of synthesizing mmm additional qubits is bounded by 21−m2^{1-m}21−m, and that the probability of preparing low-temperature Gibbs states is bounded by 22−m2^{2-m}22−m. As a consequence, we give a lower-bound the runtime of a recently studied class of repeated interaction quantum algorithms. The techniques used study states and circuits at the level of entries of their respective density and unitary matrices.
Deterministic quantum computation with one quantum bit (DQC1) [E. Knill and R. Laflamme, Phys. Rev. Lett. 81, 5672 (1998)] is a model of quantum computing where the input is restricted to containing a single qubit in a pure state and has all other qubits in a completely mixed state. Only the single pure qubit is measured at the end of the computation. While it is known that DQC1 can efficiently solve several problems for which no known classical efficient algorithms exist, the question of whether DQC1 is really more powerful than classical computation remains open. In this Letter, we introduce a slightly modified version of DQC1, which we call DQC1(k), where k output qubits are measured, and show that DQC1(k) cannot be classically efficiently simulated for any k≥3 unless the polynomial hierarchy collapses at the third level.
Deterministic quantum computation with one quantum bit (DQC1), or the one clean qubit model, [E. Knill and R. Laflamme, Phys. Rev. Lett. {\bf81}, 5672 (1998)] is a model of quantum computing where the input is the tensor product of a single pure qubit and many completely-mixed states, and only the single qubit is measured at the end of the computation. In spite of its naive appearance, the DQC1 model can efficiently solve some problems for which no classical efficient algorithms are known, and therefore it has been conjectured that the DQC1 model is more powerful than classical computing (under the assumption of $\mbox{BPP}\subsetneq\mbox{BQP}$). Here we show that the output probability distribution of the DQC1 model cannot be classically efficiently approximated (exactly within a polynomial bit length or in the fully polynomial randomized approximation scheme (FPRAS) with at most a constant error) unless $\mbox{BQP}\subseteq\mbox{BPP}$.
Future quantum information processing devices will require the use of exotic quantum states, such as specially crafted entangled states, to achieve certain desired computations on demand. Thus far, synthesis schemes for such states have been devised on a case-by-case basis using ad hoc techniques. In this paper we present a systematic method for finding a quantum circuit that can synthesize any pure or mixed n-qubit state. We then give examples of the use of our algorithm for finding synthesis pathways for especially exotic quantum states such as maximal mixed states. It is not known how to prepare general instances of such states by other means. Thus our quantum state synthesis algorithm should be of use not only in quantum information processing, but also in experimental quantum physics.
The one-clean qubit model (or the DQC1 model) is a restricted model of quantum computing where only a single qubit of the initial state is pure and others are maximally mixed. Although the model is not universal, it can efficiently solve several problems whose classical efficient solutions are not known. Furthermore, it was recently shown that if the one-clean qubit model is classically efficiently simulated, the polynomial hierarchy collapses to the second level. A disadvantage of the one-clean qubit model is, however, that the clean qubit is too clean: for example, in realistic NMR experiments, polarizations are not high enough to have the perfectly pure qubit. In this paper, we consider a more realistic one-clean qubit model, where the clean qubit is not clean, but depolarized. We first show that, for any polarization, a multiplicative-error calculation of the output probability distribution of the model is possible in a classical polynomial time if we take an appropriately large multiplicative error. The result is in strong contrast with that of the ideal one-clean qubit model where the classical efficient multiplicative-error calculation (or even the sampling) with the same amount of error causes the collapse of the polynomial hierarchy. We next show that, for any polarization lower-bounded by an inverse polynomial, a classical efficient sampling (in terms of a sufficiently small multiplicative error or an exponentially small additive error) of the output probability distribution of the model is impossible unless BQP (bounded error quantum polynomial time) is contained in the second level of the polynomial hierarchy, which suggests the hardness of the classical efficient simulation of the one nonclean qubit model.
The one-clean-qubit model (or the deterministic quantum computation with one quantum bit model) is a restricted model of quantum computing where all but a single input qubits are maximally mixed. It is known that the probability distribution of measurement results on three output qubits of the one-clean-qubit model cannot be classically efficiently sampled within a constant multiplicative error unless the polynomial-time hierarchy collapses to the third level [T. Morimae, K. Fujii, and J. F. Fitzsimons, Phys. Rev. Lett. 112, 130502 (2014)PRLTAO0031-900710.1103/PhysRevLett.112.130502]. It was open whether we can keep the no-go result while reducing the number of output qubits from three to one. Here, we solve the open problem affirmatively. We also show that the third-level collapse of the polynomial-time hierarchy can be strengthened to the second-level one. The strengthening of the collapse level from the third to the second also holds for other subuniversal models such as the instantaneous quantum polynomial model [M. Bremner, R. Jozsa, and D. J. Shepherd, Proc. R. Soc. A 467, 459 (2011)PRLAAZ1364-502110.1098/rspa.2010.0301] and the boson sampling model [S. Aaronson and A. Arkhipov, STOC 2011, p. 333]. We additionally study the classical simulatability of the one-clean-qubit model with further restrictions on the circuit depth or the gate types.
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.