論文の概要: An optimal oracle separation of classical and quantum hybrid schemes
- arxiv url: http://arxiv.org/abs/2205.04633v2
- Date: Mon, 8 Aug 2022 05:23:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-13 17:59:40.520473
- Title: An optimal oracle separation of classical and quantum hybrid schemes
- Title(参考訳): 古典的および量子的ハイブリッドスキームの最適オラクル分離
- Authors: Atsuya Hasegawa and Fran\c{c}ois Le Gall
- Abstract要約: 任意の深さパラメータ$d$に対して、計算時間古典が許されるとき、量子深さ$d$と2d+1$を分離するオラクルが存在することを示す。
これは古典的および量子的ハイブリッドスキームの最適オラクル分離を与える。
- 参考スコア(独自算出の注目度): 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.
- Abstract(参考訳): 近年、Chia, Chung and Lai (STOC 2020) と Coudron and Menda (STOC 2020) は、$\mathsf{BQP}^\mathcal{O} \neq (\mathsf{BPP^{BQNC}})^\mathcal{O} \cup (\mathsf{BQNC^{BPP}})^\mathcal{O}$ であるようなオラクル $\mathcal{O}$ が存在することを示した。
任意の深さパラメータ $d$ に対して、多項式時間古典計算が許されるとき、量子深さ $d$ と $2d+1$ を分離する神託が存在する。
これは、量子深度を2倍にすると、古典的および量子ハイブリッドスキームがより計算力を与えることを意味する。
本稿では、任意の深さパラメータ$d$に対して、多項式時間古典計算が許されるとき、量子深さ$d$と$d+1$を分離するオラクルが存在することを示す。
これは古典的および量子的ハイブリッドスキームの最適オラクル分離を与える。
この結果を証明するために、$d$-Bijective Shuffling Simon's Problem (これは、Chiaらによって考慮された$d$-Shuffling Simon's Problemの変種である) および "in-place" 置換オラクルに着想を得たオラクルを考える。
関連論文リスト
- Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳(メタデータ) (2024-01-17T18:59:38Z) - The Entangled Quantum Polynomial Hierarchy Collapses [0.0]
絡み合った量子量子階層$mathsfQEPH$が第2レベルに崩壊することを示す。
また、量子重ね合わせ(古典的確率ではない)だけがこれらの階層の計算力を増大させることを示す。
論文 参考訳(メタデータ) (2024-01-02T22:25:56Z) - A distribution testing oracle separation between QMA and QCMA [0.6906005491572401]
量子複雑性理論において、$textitnon-deterministic$ 量子計算の定義が量子証人を必要とするかどうかという長い議論である。
本稿では,各計算複雑性クラスを分離したランダム化された古典オラクルを構築することにより,この問題を進展させる。
論文 参考訳(メタデータ) (2022-10-27T12:43:56Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳(メタデータ) (2022-10-12T17:54:02Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳(メタデータ) (2022-04-22T12:37:56Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳(メタデータ) (2022-02-10T18:59:52Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
量子計算の2つのモデル: CQ_dとQC_d。
CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。
CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
論文 参考訳(メタデータ) (2022-01-06T03:10:53Z) - The Acrobatics of BQP [3.9747898273716697]
量子時間(mathsfBQP$)の挙動をブラックボックスで設定すると、$mathsfNP$のような古典的な複雑性クラスと著しく分離できることが示される。
また、独立した関心を持つかもしれない新しいツールも導入します。
ランダム制限法の「量子対応」バージョン、$mathsfAC0$回路のブロック感度に対する集中定理、スパースオークスに対するアーロンソン・アンバイニス・コンジェクチャの(証明可能な)アナログを含む。
論文 参考訳(メタデータ) (2021-11-19T19:40:05Z) - Quantum search-to-decision reductions and the state synthesis problem [0.4248594146171025]
量子アルゴリズムは古典的な決定オラクルにクエリを行い、所望の量子状態を出力することを示す。
また、逆精度まで$mathsfQMA$問題の証人を生成する量子時間アルゴリズムが存在することも示している。
また、より一般的な$textitstate合成問題$を探索し、ターゲット状態の効率的な合成を目標とする。
論文 参考訳(メタデータ) (2021-11-04T16:52:58Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。