An optimal oracle separation of classical and quantum hybrid schemes

• URL: http://arxiv.org/abs/2205.04633v2
• Date: Mon, 8 Aug 2022 05:23:10 GMT
• Title: An optimal oracle separation of classical and quantum hybrid schemes
• Authors: Atsuya Hasegawa and Fran\c{c}ois Le Gall
• Abstract summary: We show that for any depth parameter $d$, there exists an oracle that separates quantum depth $d$ and $2d+1$, when computation-time classical is allowed. This gives an optimal oracle separation of classical and quantum hybrid schemes.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, Chia, Chung and Lai (STOC 2020) and Coudron and Menda (STOC 2020) have shown that there exists an oracle $\mathcal{O}$ such that $\mathsf{BQP}^\mathcal{O} \neq (\mathsf{BPP^{BQNC}})^\mathcal{O} \cup (\mathsf{BQNC^{BPP}})^\mathcal{O}$. 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.

Related papers

Err

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.