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

Journal of the ACM

Computing with highly mixed states

Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani

Published May 1, 2006• 34 citations
Publisher

Abstract

Device initialization is a difficult challenge in some proposed realizations of quantum computers, and as such, must be treated as a computational resource. The degree of initialization can be quantified by k , the number of clean qubits in the initial state of the register. In this article, we show that unless m ∈ O ( k + log n ), oblivious (gate-by-gate) simulation of an ideal m -qubit quantum circuit by an n -qubit circuit with k clean qubits is impossible. Effectively, this indicates that there is no avoiding physical initialization of a quantity of qubits proportional to that required by the best ideal quantum circuit.

DOI
10.1145/1147954.1147962

Related papers

Computing with highly mixed states

Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani

We consider quantum computing in the k-qubit model where the starting state of a quantum computer consists of k qubits in a pure state and n-k qubits in a maximally mixed state. We ask the following question: is there a general method for simulating an arbitrary m-qubit pure state quantum computation by a quantum computation in the k-qubit model? We show that, under certain constraints, this is impossible, unless m=O(k+ log n).

arXiv:quant-ph/0003136•Mar 29, 2000•14 citations

What Limits the Simulation of Quantum Computers?

Yiqing Zhou, E. Miles Stoudenmire, Xavier Waintal

An ultimate goal of quantum computing is to perform calculations beyond the reach of any classical computer.It is therefore imperative that useful quantum computers be very difficult to simulate classically, otherwise classical computers could be used for the applications envisioned for the quantum ones.Perfect quantum computers are unarguably exponentially difficult to simulate: the classical resources required grow exponentially with the number of qubits N or the depth D of the circuit.This difficulty has triggered recent experiments on deep, random circuits that aim to demonstrate that quantum devices may already perform tasks beyond the reach of classical computing.These real quantum computing devices, however, suffer from many sources of decoherence and imprecision which limit the degree of entanglement that can actually be reached to a fraction of its theoretical maximum.They are characterized by an exponentially decaying fidelity F ∼ ð1 -ϵÞ ND with an error rate ϵ per operation as small as ≈1% for current devices with several dozen qubits or even smaller for smaller devices.In this work, we provide new insight on the computing capabilities of real quantum computers by demonstrating that they can be simulated at a tiny fraction of the cost that would be needed for a perfect quantum computer.Our algorithms compress the representations of quantum wave functions using matrix product states, which are able to capture states with low to moderate entanglement very accurately.This compression introduces a finite error rate ϵ so that the algorithms closely mimic the behavior of real quantum computing devices.The computing time of our algorithm increases only linearly with N and D in sharp contrast with exact simulation algorithms.We illustrate our algorithms with simulations of random circuits for qubits connected in both one-and twodimensional lattices.We find that ϵ can be decreased at a polynomial cost in computing power down to a minimum error ϵ ∞ .Getting below ϵ ∞ requires computing resources that increase exponentially with ϵ ∞ =ϵ.For a two-dimensional array of N ¼ 54 qubits and a circuit with control-Z gates, error rates better than state-of-the-art devices can be obtained on a laptop in a few hours.For more complex gates such as a SWAP gate followed by a controlled rotation, the error rate increases by a factor 3 for similar computing time.Our results suggest that, despite the high fidelity reached by quantum devices, only a tiny fraction ð∼10 -8 Þ of the system Hilbert space is actually being exploited.

arXiv:2002.07730•Physical Review X•Nov 23, 2020•254 citations

Computing with highly mixed states (extended abstract)

Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani

We consider quantum computing in the one-qubit model where the starting state of a quantum computer consists of k qubits in a pure state and n − k qubits in a maximally mixed state. We ask the following question: is there a general method for simulating an arbitrary m-qubit pure state quantum computation by a quantum computation in the k-qubit model? We show that, under certain constraints, this is impossible, unless m = O(k + log n). 1.

ACM Symposium on Theory of Computing (STOC)•May 1, 2000•9 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•59 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•15 citations

Gray code and the initialization problem of NMR quantum computers

Ryuichi Sawae, Toshio Sakata, M. Tei +2 more

Abstract The initialization of states is of importance in nuclear magnetic resonance quantum computing systems. In this article it is shown that the initialization ofn‐qubits states can be realized via a sequence of controlled‐not quantum gates from any mixed state. We present a general algorithm and its optimization to construct a circuit of controlled‐not quantum gates that realizes the initialization using the concept of Gray Codes. © 2003 Wiley Periodicals, Inc. Int J Quantum Chem, 2003

International Journal of Quantum Chemistry•Jan 1, 2003•3 citations
Device initialization is a difficult challenge in some proposed realizations of quantum computers, and as such, must be treated as a computational resource. The degree of initialization can be quantified by k , the number of clean qubits in the initial state of the register. In this article, we show that unless m ∈ O ( k + log n ), oblivious (gate-by-gate) simulation of an ideal m -qubit quantum circuit by an n -qubit circuit with k clean qubits is impossible. Effectively, this indicates that there is no avoiding physical initialization of a quantity of qubits proportional to that required by the best ideal quantum circuit.
An ultimate goal of quantum computing is to perform calculations beyond the reach of any classical computer.It is therefore imperative that useful quantum computers be very difficult to simulate classically, otherwise classical computers could be used for the applications envisioned for the quantum ones.Perfect quantum computers are unarguably exponentially difficult to simulate: the classical resources required grow exponentially with the number of qubits N or the depth D of the circuit.This difficulty has triggered recent experiments on deep, random circuits that aim to demonstrate that quantum devices may already perform tasks beyond the reach of classical computing.These real quantum computing devices, however, suffer from many sources of decoherence and imprecision which limit the degree of entanglement that can actually be reached to a fraction of its theoretical maximum.They are characterized by an exponentially decaying fidelity F ∼ ð1 -ϵÞ ND with an error rate ϵ per operation as small as ≈1% for current devices with several dozen qubits or even smaller for smaller devices.In this work, we provide new insight on the computing capabilities of real quantum computers by demonstrating that they can be simulated at a tiny fraction of the cost that would be needed for a perfect quantum computer.Our algorithms compress the representations of quantum wave functions using matrix product states, which are able to capture states with low to moderate entanglement very accurately.This compression introduces a finite error rate ϵ so that the algorithms closely mimic the behavior of real quantum computing devices.The computing time of our algorithm increases only linearly with N and D in sharp contrast with exact simulation algorithms.We illustrate our algorithms with simulations of random circuits for qubits connected in both one-and twodimensional lattices.We find that ϵ can be decreased at a polynomial cost in computing power down to a minimum error ϵ ∞ .Getting below ϵ ∞ requires computing resources that increase exponentially with ϵ ∞ =ϵ.For a two-dimensional array of N ¼ 54 qubits and a circuit with control-Z gates, error rates better than state-of-the-art devices can be obtained on a laptop in a few hours.For more complex gates such as a SWAP gate followed by a controlled rotation, the error rate increases by a factor 3 for similar computing time.Our results suggest that, despite the high fidelity reached by quantum devices, only a tiny fraction ð∼10 -8 Þ of the system Hilbert space is actually being exploited.
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 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.
Abstract The initialization of states is of importance in nuclear magnetic resonance quantum computing systems. In this article it is shown that the initialization ofn‐qubits states can be realized via a sequence of controlled‐not quantum gates from any mixed state. We present a general algorithm and its optimization to construct a circuit of controlled‐not quantum gates that realizes the initialization using the concept of Gray Codes. © 2003 Wiley Periodicals, Inc. Int J Quantum Chem, 2003