Distinguishing Short Quantum Computations

Understand

Distinguishing logarithmic depth quantum circuits on mixed states is shown to be complete for QIP, the class of problems having quantum interactive proof systems.

• Circuits in this model can represent arbitrary quantum processes, and thus this result has implications for the verification of implementations of quantum algorithms.
• The distinguishability problem is also complete for QIP on constant depth circuits containing the unbounded fan-out gate.
• These results are shown by reducing a QIP-complete problem to a logarithmic depth version of itself using a parallelization technique.