2026-08-18T21:51:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17291 2024-03-06T10:59:22Z ddc:004 open_access

An Optimal Oracle Separation of Classical and Quantum Hybrid Schemes Hasegawa, Atsuya Le Gall, François small-depth quantum circuit hybrid quantum computer oracle separation Recently, Chia, Chung and Lai (STOC 2020) and Coudron and Menda (STOC 2020) have shown that there exists an oracle 𝒪 such that BQP^𝒪 ≠ (BPP^BQNC)^𝒪 ∪ (BQNC^BPP)^𝒪. In fact, Chia et al. proved a stronger statement: 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 paper, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Atsuya Hasegawa and François Le Gall 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.6 urn:nbn:de:0030-drops-172918 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.6 eng https://creativecommons.org/licenses/by/4.0/legalcode