One Clean Qubit
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ea/One_clean_qubit.png/220px-One_clean_qubit.png)
The One Clean Qubit model of computation is performed an qubit system with one pure state and maximally mixed states.[1] This model was motivated by highly mixed states that are prevalent in Nuclear magnetic resonance quantum computers. It's described by the density matrix , where I is the identity matrix. In computational complexity theory, DQC1; also known as the Deterministic quantum computation with one clean qubit is the class of decision problems solvable by a one clean qubit machine in polynomial time, upon measuring the first qubit, with an error probability of at most 1/poly(n) for all instances.[2]
Error Bounds and Composability
[edit]The most standard definition of DQC1 requires that measuring the output qubit correctly accepts or rejects the input, with error at most for specified some polynomial q, given a gap in acceptance probabilities of for NO instances and for YES instances. Most probabilistic classes, such as BPP, BQP, and RP are agnostic to the precise probability gap, because any polynomial acceptance gap can be amplified to a fixed gap such as (1/3,2/3). A notable outlier is PP, which permits exponentially small gaps.
DQC1 does not admit an obvious notion of parallel composability or amplification: there is no clear construction to transform a circuit with, say, a (2/5,3/5) acceptance gap into a more accurate (1/5,4/5) acceptance gap.
It is known that DQC1 offers composability in the sense that the "one" clean qubit can be upgraded to "two" clean qubits, or even many clean qubits, without modifying the class[3] Computation with Unitaries and One Pure Qubit. D. J. Shepherd.[4]</ref> It is also not strengthened by measuring all of these clean qubits (as opposed to just the first clean qubit).
Relation to other classes
[edit]Because as many as qubits are permitted,[3] DQC1 contains all logspace computations. It is closed under L reductions as well. It is not known to contain BPP or even P. It is contained in BQP, and it is conjectured that this is containment is strict.
It is known that simulating the sampling problem even for 3 output qubits is classically hard, in the sense that it would imply a PH collapse.[5]
The term DQC1 has been used to instead refer to decision problems solved by a polynomial time classical circuit that adaptively makes queries to polynomially many DQC1 circuits.[6] In this sense of use, the class naturally contains all of BPP, and the power of the class is focused on the "inherently quantum" power.
Trace Estimation
[edit]Trace estimation is complete for DQC1.[7] Let be a unitary matrix. Given a state , the Hadamard test can estimate where is the probability that the measured clean qubit is 0. mixed state inputs can be simulated by letting be chosen uniformly at random from computational basis states. When measured, the probability that the final result is 0 is[2] To estimate the imaginary part of the , the clean qubit is initialized to instead of .
DQC1-complete Problems
[edit]In addition to unitary trace estimation, estimating a coefficient in the Pauli decomposition of a unitary and approximating the Jones polynomial at a fifth root of unity are also DQC1-complete. In fact, trace estimation is a special case of Pauli decomposition coefficient estimation.[8]
References
[edit]- ^ Knill, Emanuel; Laflamme, Raymond Laflamme (1998). "Power of One Bit of Quantum Information". Physical Review Letters. 81 (25): 5672–5675. arXiv:quant-ph/9802037. Bibcode:1998PhRvL..81.5672K. doi:10.1103/PhysRevLett.81.5672. S2CID 118931256.
- ^ a b Peter W. Shor (2008). "Estimating Jones polynomials is a complete problem for one clean qubit". Quantum Information & Computation. 8 (8&9): 681–714. arXiv:0707.2831. doi:10.26421/QIC8.8-9-1. S2CID 2235861.
- ^ a b Shepherd, Dan (2006). "Computation with Unitaries and One Pure Qubit". arXiv:quant-ph/0608132.
- ^ Shepherd's paper adopts the nonstandard notation of DQC1 referring only to the circuits and sampling problems, and use BQ1P to refer to decision problems.
- ^ Morimae, Tomoyuki; Fujii, Keisuke; Fitzsimons, Joseph F. (2014). "Hardness of Classically Simulating the One-Clean-Qubit Model". Physical Review Letters. 112 (13): 130502. arXiv:1312.2496. Bibcode:2014PhRvL.112m0502M. doi:10.1103/PhysRevLett.112.130502. PMID 24745398. S2CID 14437218.
- ^ Chowdhury, Anirban N.; Somma, Rolando D.; Subaşı, Yiğit (2021). "Computing partition functions in the one-clean-qubit model". Physical Review A. 103 (3): 032422. arXiv:1910.11842. Bibcode:2021PhRvA.103c2422C. doi:10.1103/PhysRevA.103.032422. S2CID 204901397.
- ^ Shepherd, Dan (2006). "Computation with Unitaries and One Pure Qubit". arXiv:quant-ph/0608132.
- ^ Cade, Chris; Montanaro, Ashley (2017). "The Quantum Complexity of Computing Schatten p-norms". arXiv:1706.09279 [quant-ph].