One Clean Qubit

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
One clean qubit quantum circuit that estimates the trace of

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 with an error probability of at most 1/3 for all instances.[2]

Trace Estimation[edit]

Trace estimation is complete for DQC1.[3] 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.[4]


  1. ^ Knill, Emanuel; Laflamme, Raymond Laflamme (1998). "Power of One Bit of Quantum Information". Physical Review Letters. 81 (25): 5672–5675. arXiv:quant-ph/9802037. doi:10.1103/PhysRevLett.81.5672. S2CID 118931256.
  2. ^ 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.
  3. ^ Shepherd, Dan (2006). "Computation with Unitaries and One Pure Qubit". arXiv:quant-ph/0608132.
  4. ^ Cade, Chris; Montanaro, Ashley (2017). "The Quantum Complexity of Computing Schatten p-norms". arXiv:1706.09279 [quant-ph].