# One Clean Qubit

One clean qubit quantum circuit that estimates the trace of ${\displaystyle U}$

The One Clean Qubit model of computation is performed an ${\displaystyle n}$ qubit system with one pure state and ${\displaystyle 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 ${\displaystyle \rho =\left|0\right\rangle \langle 0|\otimes {\frac {I}{2}}}$, 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

Trace estimation is complete for DQC1.[3] Let ${\displaystyle U}$ be a unitary ${\displaystyle 2^{n}\times 2^{n}}$ matrix. Given a state ${\displaystyle |\psi \rangle }$, the Hadamard test can estimate ${\displaystyle \left\langle \psi \right|U\left|\psi \right\rangle }$ where ${\textstyle {\frac {1}{2}}+{\frac {1}{2}}{\mathcal {Re}}(\left\langle \psi \right|U\left|\psi \right\rangle )}$ is the probability that the measured clean qubit is 0. ${\displaystyle I/2^{n}}$ mixed state inputs can be simulated by letting ${\displaystyle |\psi \rangle }$ be chosen uniformly at random from ${\displaystyle 2^{n}}$ computational basis states. When measured, the probability that the final result is 0 is[2]

${\displaystyle {\frac {1}{2^{n}}}\sum _{x\subset \{0,1\}^{n}}{\frac {1+{\mathcal {Re}}\left\langle x\right|U\left|x\right\rangle }{2}}={\frac {1}{2}}+{\frac {1}{2}}{\frac {{\mathcal {Re}}(Tr(U))}{2^{n}}}.}$
To estimate the imaginary part of the ${\displaystyle Tr(U)}$, the clean qubit is initialized to ${\textstyle {\frac {1}{\sqrt {2}}}\left(\left|0\right\rangle -i\left|1\right\rangle \right)}$ instead of ${\textstyle {\frac {1}{\sqrt {2}}}\left(\left|0\right\rangle +\left|1\right\rangle \right)}$.

## 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.[4]

## References

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].