One Clean Qubit

Trace estimation is complete for DQC1.[3] Let ${\displaystyle U}$ be a unitary ${\displaystyle 2^{n}}$ × ${\displaystyle 2^{n}}$ matrix. Given a state ${\displaystyle |\psi \rangle }$, the Hadamard test can estimate ${\displaystyle \left\langle \psi \mid U\mid \psi \right\rangle }$ where ${\displaystyle {\frac {1}{2}}+{\frac {1}{2}}{\mathcal {Re}}(\left\langle \psi \mid U\mid \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 ${\displaystyle {\frac {1}{2^{n}}}\sum _{x\subset \{0,1\}^{n}}{\frac {1+{\mathcal {Re}}\left\langle x\mid U\mid x\right\rangle }{2}}={\frac {1}{2}}+{\frac {1}{2}}{\frac {{\mathcal {Re}}(Tr(U))}{2^{n}}}}$.[2] To estimate the imaginary part of the ${\displaystyle Tr(U)}$, the clean qubit is initialized to ${\displaystyle {\frac {1}{\sqrt {2}}}\left(\left|0\right\rangle -i\left|1\right\rangle \right)}$ instead of ${\displaystyle {\frac {1}{\sqrt {2}}}\left(\left|0\right\rangle +\left|1\right\rangle \right)}$.

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]