An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes

Math/CS Seminar Atsuya Hasegawa (University of Tokyo)

Recently, Chia, Chung and Lai (JACM 2023) have shown that, for any depth parameter d, there exists an oracle that separates quantum depth d and 2d+1, when polynomial-time classical computation is allowed. This implies that relative to an oracle, doubling quantum depth gives classical and quantum hybrid schemes more computational power.

In this talk, we show that for any depth parameter d, there exists an oracle that separates quantum depth d and d+1, when polynomial-time classical computation is allowed. This gives an optimal oracle separation of classical and quantum hybrid schemes. To prove our result, we consider d-Bijective Shuffling Simon's Problem (which is a variant of d-Shuffling Simon's Problem considered by Chia et al.) and an oracle inspired by an "in-place" permutation oracle.c

Join Zoom Meeting
https://uwaterloo.zoom.us/j/96785708079?pwd=akwwSkhCczFZRG4zNGdRMEhQa1dlQT09

Meeting ID: 967 8570 8079
Passcode: 423237