# One Clean Qubit One clean qubit quantum circuit that estimates the trace of $U$ The One Clean Qubit model of computation is performed an $n$ qubit system with one pure state and $n-1$ 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 $\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.

## Trace Estimation

Trace estimation is complete for DQC1. Let $U$ be a unitary $2^{n}\times 2^{n}$ matrix. Given a state $|\psi \rangle$ , the Hadamard test can estimate $\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. $I/2^{n}$ mixed state inputs can be simulated by letting $|\psi \rangle$ be chosen uniformly at random from $2^{n}$ computational basis states. When measured, the probability that the final result is 0 is

${\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 $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.