論文の概要: 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]による最近の量子性構築の証明を用いてインスタンス化できる。
関連論文リスト
- Quantum-Computable One-Way Functions without One-Way Functions [0.6349503549199401]
古典的なオラクルを構築し、$mathsfP = MathsfNP$, but quantum-computable quantum-secure trapdoor one-way function が存在する。
この結果から,複数コピーの擬似乱数状態と擬似乱数ユニタリー,古典通信の公開鍵暗号,シグネチャ,暗黙の転送方式が示唆された。
論文 参考訳（メタデータ） (2024-11-04T19:40:01Z) - Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。
驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。
約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
論文 参考訳（メタデータ） (2024-11-01T18:00:56Z) - Improved separation between quantum and classical computers for sampling and functional tasks [3.618534280726541]
本稿では、量子コンピュータが古典的コンピュータを超えた計算が可能であるという既存の証拠をさらに強調する。
i)ポストセレクションを持つ量子コンピュータは、ポストセレクションを持つ古典的コンピュータと同じくらい強力である。
正確な数え上げオラクルで解ける問題と近似数え上げオラクルで解ける問題の間に同値性が存在すると証明すると、階層構造はその第2レベルに崩壊する。
論文 参考訳（メタデータ） (2024-10-28T11:30:10Z) - Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
近年の分離により、階層構造が崩壊しても持続する硬さの源から量子暗号を構築する可能性が高まっている。
量子暗号は、$mathsfP#P notsubseteq mathsf(io)BQP/qpoly$という非常に穏やかな仮定に基づいている。
論文 参考訳（メタデータ） (2024-09-23T17:45:33Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。