10.4230/LIPIcs.STACS.2008.1322
Rosgen, Bill
Distinguishing Short Quantum Computations
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany
2008
Computer Science
000 Computer science, knowledge, general works
Herbstritt, Marc
2008-02-06
eng
ConferencePaper
12 pages
application/pdf
1.0
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC-BY-NC-ND)
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.