論文の概要: Quantum Advantage has Few Complexity Implications
- arxiv url: http://arxiv.org/abs/2611.05303v1
- Date: Tue, 03 Nov 2026 18:14:46 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-07 13:06:47.959911
- Title: Quantum Advantage has Few Complexity Implications
- Title(参考訳): 量子アドバンテージは複雑度にほとんど影響しない
- Abstract要約: 量子性の証明は$mathsfP = MathsfNP$ のときに存在することを示す。
また、$mathsfBQP = MathsfQCMA$ のとき、(量子検証器)不定形状態の準備が可能であることも示している。
- 参考スコア(独自算出の注目度): 7.365059987835511
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We consider the complexity implications of proofs of quantumness and (quantum verifier) oblivious state preparation. We show that both of these objects can coexist with the easiness of nondeterministic computation. That is, we give evidence that proofs of quantumness can exist when $\mathsf{P} = \mathsf{NP}$ and that (quantum verifier) oblivious state preparation can exist when $\mathsf{BQP} = \mathsf{QCMA}$. In particular, we give a classical oracle relative to which (1) $\mathsf{P}^\mathcal{O} = \mathsf{NP}^\mathcal{O}$ (2) $\mathsf{BQP}^\mathcal{O} = \mathsf{PSPACE}^\mathcal{O}$ (3) Proofs of quantumness exist. In particular, there exists a language in $\mathsf{IP}^\mathcal{O} \subseteq \mathsf{BQP}^\mathcal{O}$ which is hard on average against $\mathsf{P}^\mathcal{O}/poly$. We give a unitary oracle such that (1) $\mathsf{BQP}^\mathcal{O} = \mathsf{QCMA}^\mathcal{O}$ (2) Quantum verifier oblivious state preparation exists. These oracle separations directly imply a number of related consequences. For example, our first result implies that proofs of quantumness cannot be used to construct classical or quantum cryptography with a relativizing proof. Our second result implies that quantum computation/classical communication oblivious transfer cannot be used to construct post-quantum one-way functions with a relativizing proof.
- Abstract(参考訳): 量子性証明と(量子検証器)暗黙的状態準備の複雑さを考察する。
両対象が非決定論的計算の容易性と共存可能であることを示す。
すなわち、$\mathsf{P} = \mathsf{NP}$ のとき量子性の証明が存在し、$\mathsf{BQP} = \mathsf{QCMA}$ のとき、(量子検証器)可観測状態の準備が存在するとき、その証拠を与える。
特に、(1) $\mathsf{P}^\mathcal{O} = \mathsf{NP}^\mathcal{O}$ (2) $\mathsf{BQP}^\mathcal{O} = \mathsf{PSPACE}^\mathcal{O}$ (3) 量子性の証明が存在する古典的なオラクルを与える。
特に、$\mathsf{IP}^\mathcal{O} \subseteq \mathsf{BQP}^\mathcal{O}$は、$\mathsf{P}^\mathcal{O}/poly$に対して平均的に難しい言語が存在する。
1) $\mathsf{BQP}^\mathcal{O} = \mathsf{QCMA}^\mathcal{O}$ (2) Quantum verifier oblivious state prepared。
これらのオラクルの分離は、いくつかの関連する結果を直接意味している。
例えば、我々の最初の結果は、量子性の証明は古典的あるいは量子的暗号を相対的証明で構築するのに使用できないことを示唆している。
2つ目の結果は、量子計算/古典的通信の難読化は、相対化証明を用いて量子後片道関数を構築するには利用できないことを示唆している。
関連論文リスト
- Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation [40.97629361826537]
我々は,古典的に検証可能な量子優位性と,量子不識別性難読化(qiO)を用いた計算の古典的検証のためのプロトコルを構築した。
我々の結果はAaronsonとZhangの$emphpeaked random circuit sample(arXiv:2404.14493)に基づく量子優位提案のための厳密な暗号基盤と見なすことができる。
論文 参考訳(メタデータ) (2026-09-30T17:49:01Z) - Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy [0.7321157455672144]
証明に特有の量子古典的PCPの制限は、そのパワーを低下させるものではないことを示す。
また、カルプ・リプトンの定理の非一様量子類似性も証明する。
これらの結果は、量子証明システムの構造に関する新たな洞察を与える。
論文 参考訳(メタデータ) (2025-06-24T16:59:50Z) - Quantum oracles for the finite element method [45.200826131319815]
本研究では,N倍の剛性および質量行列のブロックエンコーディングに使用されるオラクルの実装に必要な量子ルーチンについて検討した。
本稿では, 要素幾何学, 平方根の計算, 条件演算の実装など, 必要なオラクルを構築する方法を示す。
論文 参考訳(メタデータ) (2025-04-28T14:28:31Z) - Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。
驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。
約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
論文 参考訳(メタデータ) (2024-11-01T18:00:56Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳(メタデータ) (2024-02-29T01:35:46Z) - Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower
bounds [1.3927943269211591]
本研究は、$mathsfPH$の量子検証に基づく3つの一般化を研究する。
まず、[GSSSY22] から、崩壊定理と$mathsfQCPH$に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。
我々は、$mathsfpureQPH$に対する一方の誤り低減と、これらの量子変量$mathsfPH$に関する最初の境界を示す。
論文 参考訳(メタデータ) (2024-01-03T09:12:25Z) - Nonlocality under Computational Assumptions [51.020610614131186]
相関の集合が非局所であるとは、空間的分離な当事者がランダム性を共有し、局所的な操作を実行することによって再現できないことである。
ランダム性や量子時間計算によって再現できない局所的な(効率のよい)測定結果が存在することを示す。
論文 参考訳(メタデータ) (2023-03-03T16:53:30Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳(メタデータ) (2022-10-12T17:54:02Z) - Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。
密度行列 $rho$ は可観測物の期待値から決定できると仮定される。
アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
論文 参考訳(メタデータ) (2021-12-14T16:29:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。