Events
Spring 2020

Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)

Feb. 11, 2020 4:00 pm5:00 pm

Add to Calendar

Location: 

Calvin Lab Auditorium, Room 116

A conjecture of Jozsa states that any polynomial-time quantum computation can be simulated by polylogarithmic-depth quantum computation interleaved with polynomial-depth classical computation. Separately, Aaronson conjectured that there exists an oracle that separates BQP and BPP^BQNC. These conjectures are intriguing allusions to the unresolved potential of combining classical and low-depth quantum computation. In this work we show that the Welded Tree Problem, which is an oracle problem that can be solved in quantum polynomial time as shown by Childs et al., cannot be solved in BPP^BQNC, nor can it be solved in the class that Jozsa describes.  This proves Aaronson's oracle separation conjecture and provides a counterpoint to Jozsa's conjecture relative to the Welded Tree oracle problem.  More precisely, we define two complexity classes, HQC and JC whose languages are decided by two different families of interleaved quantum-classical circuits.  HQC contains BPP^BQNC and is therefore relevant to Aaronson's conjecture, while JC captures the model of computation that Jozsa considers. We show that the Welded Tree Problem gives an oracle separation between eitherof {JC, HQC}and BQP.  Therefore, even when interleaved with arbitrary polynomial-time classical computation, greater "quantum depth'' leads to strictly greater computational ability in this relativized setting.