論文の概要: Quantum Depth in the Random Oracle Model
- arxiv url: http://arxiv.org/abs/2210.06454v1
- Date: Wed, 12 Oct 2022 17:54:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-22 19:23:41.708564
- Title: Quantum Depth in the Random Oracle Model
- Title(参考訳): ランダムOracleモデルにおける量子深さ
- Authors: Atul Singh Arora and Andrea Coladangelo and Matthew Coudron and
Alexandru Gheorghiu and Uttam Singh and Hendrik Waldner
- Abstract要約: 浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
- 参考スコア(独自算出の注目度): 57.663890114335736
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We give a comprehensive characterization of the computational power of
shallow quantum circuits combined with classical computation. Specifically, for
classes of search problems, we show that the following statements hold,
relative to a random oracle:
(a) $\mathsf{BPP}^{\mathsf{QNC}^{\mathsf{BPP}}} \neq \mathsf{BQP}$. This
refutes Jozsa's conjecture [QIP 05] in the random oracle model. As a result,
this gives the first instantiatable separation between the classes by replacing
the oracle with a cryptographic hash function, yielding a resolution to one of
Aaronson's ten semi-grand challenges in quantum computing.
(b) $\mathsf{BPP}^{\mathsf{QNC}} \nsubseteq \mathsf{QNC}^{\mathsf{BPP}}$ and
$\mathsf{QNC}^{\mathsf{BPP}} \nsubseteq \mathsf{BPP}^{\mathsf{QNC}}$. This
shows that there is a subtle interplay between classical computation and
shallow quantum computation. In fact, for the second separation, we establish
that, for some problems, the ability to perform adaptive measurements in a
single shallow quantum circuit, is more useful than the ability to perform
polynomially many shallow quantum circuits without adaptive measurements.
(c) There exists a 2-message proof of quantum depth protocol. Such a protocol
allows a classical verifier to efficiently certify that a prover must be
performing a computation of some minimum quantum depth. Our proof of quantum
depth can be instantiated using the recent proof of quantumness construction by
Yamakawa and Zhandry [STOC 22].
- Abstract(参考訳): 浅層量子回路の計算能力を古典計算と組み合わせて包括的に評価する。
具体的には,探索問題のクラスについて,ランダムなオラクルに対して,以下の文が成り立つことを示す。
(a) $\mathsf{BPP}^{\mathsf{QNC}^{\mathsf{BPP}}} \neq \mathsf{BQP}$
これはランダムオラクルモデルにおけるjozsaの予想[qip 05]を反論する。
その結果、オラクルを暗号ハッシュ関数に置き換え、量子コンピューティングにおけるアーロンソンの10の半粒課題の1つに分解することで、クラス間での最初の即時分離を与える。
(b) $\mathsf{BPP}^{\mathsf{QNC}} \nsubseteq \mathsf{QNC}^{\mathsf{BPP}}$および$\mathsf{QNC}^{\mathsf{BPP}} \nsubseteq \mathsf{BPP}^{\mathsf{QNC}}$
これは古典計算と浅い量子計算の間に微妙な相互作用が存在することを示している。
実際、第2の分離では、ある問題に対して、1つの浅量子回路で適応測定を行う能力は、適応測定なしで多項式的に多くの浅量子回路を実行する能力よりも有用であることを示す。
(c)量子深度プロトコルの2メッセージ証明が存在する。
このようなプロトコルにより、古典的な検証者は、証明者が最小の量子深さの計算を行う必要があることを効率的に証明することができる。
量子深みの証明は、山川とzhandry [stoc 22]による最近の量子性構築の証明を用いてインスタンス化できる。
関連論文リスト
- The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳(メタデータ) (2024-02-29T01:35:46Z) - Succinct Classical Verification of Quantum Computation [30.91621630752802]
量子計算のための古典的簡潔な対話的引数(BQP)を構築する。
我々のプロトコルは、識別不能難読化(iO)と学習エラー(LWE)の事後セキュリティを前提として安全である。
論文 参考訳(メタデータ) (2022-06-29T22:19:12Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - An optimal oracle separation of classical and quantum hybrid schemes [0.0]
任意の深さパラメータ$d$に対して、計算時間古典が許されるとき、量子深さ$d$と2d+1$を分離するオラクルが存在することを示す。
これは古典的および量子的ハイブリッドスキームの最適オラクル分離を与える。
論文 参考訳(メタデータ) (2022-05-10T02:31:19Z) - 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) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳(メタデータ) (2021-07-05T17:45:41Z) - Quantum Pseudorandomness and Classical Complexity [0.08158530638728499]
暗号擬似乱数量子状態と擬似乱数ユニタリ変換が存在することを示す。
本稿では、暗号、複雑性理論、量子トモグラフィーにおけるこれらの結果の影響について論じる。
論文 参考訳(メタデータ) (2021-03-16T20:54:12Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳(メタデータ) (2020-12-03T14:03:20Z) - Simpler Proofs of Quantumness [16.12500804569801]
量子性の証明は、量子デバイスが古典的なデバイスでは不可能な計算タスクを実行できることを示す方法である。
現在、量子性の証明を示すための3つのアプローチがある。
トラップドアの爪のない関数をベースとした量子性の2次元証明(Challenge-Response)を与える。
論文 参考訳(メタデータ) (2020-05-11T01:31:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。