Deterministic Quantum Computation with One Clean Qubit (DQC1)

Abstract

The Deterministic Quantum Computation with One Clean Qubit (DQC1) model provides a framework for evaluating the computational power of highly mixed quantum states. Motivated by the constraints of physical quantum system implementations, DQC1 relies on initializing only a single control qubit in a pure state while the remaining register is maximally mixed. This work provides a comprehensive characterization of the DQC1 complexity class and surveys its algorithmic capabilities. We first explore the model’s foundational mechanism of unitary trace estimation an rigorously prove that supplementing the system with a logarithmic number of pure ancilla qubits (k-clean-qubits) does not alter its fundamental complexity class. Furthermore, we determine the limits of this model by demonstrating its inability to obliviously simulate universal Bounded Error Quantum Polynomial-Time (BQP) circuits, establishing a definitive difference between DQC1 and BQP. Finally, we examine applications that leverage this architecture: the #P-hard approximation of Jones polynomials for trace closures of braids, the demonstration of quantum advantage driven by quantum discord rather than entanglement, the noise-resilient estimation of kernels for supervised quantum machine learning, and the evaluation of constrained Quadratically Signed Weight Enumerators (QSWEs). Together, these analyses highlight DQC1 as a bridge between classical and quantum computing, capable of efficiently solving specific, classically intractable problems despite limitations on quantum purity.