Class Description

DQC1: Deterministic Quantum Computing with 1 Clean Bit

The class of problems solvable by a BQP machine in which a single qubit is initialized to the '0' state, and the remaining qubits are initialized to the maximally mixed state.

We need to stipulate that there are no "strong measurements" -- intermediate measurements on which later operations are conditioned -- since otherwise we can do all of BQP by first initializing the computer to the all-0 state.

[ASV00] showed that if DQC1 = BQP, something other than gate-by-gate simulation will be needed to show this.

[SJ08] showed that approximating the Jones polynomial at a fifth root of unity for the trace closure of a braid is complete for DQC1.

Linked From

No class.