One Clean Qubit

The One Clean Qubit model of computation is performed an formula_1 qubit system with one pure state and formula_2 maximally mixed states. This model was motivated by highly mixed states that are prevalent in Nuclear magnetic resonance quantum computers. It's described by the density matrix formula_3, 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 with an error probability of at most 1/3 for all instances.
Trace Estimation.
Trace estimation is complete for DQC1. Let formula_4 be a unitary formula_5 × formula_5 matrix. Given a state formula_7, the Hadamard test can estimate formula_8 where formula_9 is the probability that the measured clean qubit is 0. formula_10 mixed state inputs can be simulated by letting formula_7 be chosen uniformly at random from formula_5 computational basis states. When measured, the probability that the final result is 0 is formula_13. To estimate the imaginary part of the formula_14, the clean qubit is initialized to formula_15 instead of formula_16.
DQC1-complete Problems.
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.