On the Complexity of Hybrid Quantum Computation

Watch a conference talk from TQC 2023 exploring the computational capabilities of hybrid quantum systems, where Alexandru Gheorghiu presents groundbreaking research on combining shallow quantum circuits with classical computation. Delve into comprehensive findings that challenge Jozsa's conjecture in the random oracle model, examine the intricate relationship between classical and shallow quantum computation, and discover a novel 2-message proof of quantum depth protocol. Learn about the subtle advantages of adaptive measurements in shallow quantum circuits and understand the implications for quantum computing complexity theory through detailed mathematical proofs and theoretical frameworks. Follow along as key concepts are broken down across topics including computation models, relationships between different computational approaches, the Random Oracle Model, and the DeQuan Depth Protocol, concluding with open questions in quantum decision problems.