One Clean Qubit Explained

The One Clean Qubit model of computation is performed an

qubit system with one pure state and

n-1

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

\rho=\left|0\right\rangle\langle0| ⊗

	I
	2^n-1

, where

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.

Error Bounds and Composability

The most standard definition of DQC1 requires that measuring the output qubit correctly accepts or rejects the input, with error at most

1/q(n)

for specified some polynomial q, given a gap in acceptance probabilities of

[0,1/2-1/q(n)]

for NO instances and

[1/2+1/q(n),1]

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

log(n)

many clean qubits, without modifying the class^[2] Computation with Unitaries and One Pure Qubit.D. J. Shepherd.^[3]

Notes and References

quant-ph/9802037 . Knill. Emanuel . Laflamme . Raymond Laflamme . Power of One Bit of Quantum Information. Physical Review Letters. 1998. 81. 25. 5672–5675. 10.1103/PhysRevLett.81.5672. 1998PhRvL..81.5672K . 118931256.
quant-ph/0608132 . Shepherd . Dan . Computation with Unitaries and One Pure Qubit . 2006 .
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.