論文の概要: On the Complexity of Decoded Quantum Interferometry
- arxiv url: http://arxiv.org/abs/2509.14443v1
- Date: Wed, 17 Sep 2025 21:31:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-19 17:26:52.980415
- Title: On the Complexity of Decoded Quantum Interferometry
- Title（参考訳）: 復号化量子干渉計の複雑さについて
- Authors: Kunal Marwaha, Bill Fefferman, Alexandru Gheorghiu, Vojtech Havlicek,
- Abstract要約: 最近提案された近似最適化のための量子アルゴリズムであるDecoded Quantum Interferometry (DQI) の複雑さについて検討した。
我々は、DQIは古典的なシミュレートが困難であり、その硬さは指数関数的に大きな隠れ部分集合を見つけることから生じると論じる。
- 参考スコア（独自算出の注目度）: 39.951444958798014
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the complexity of Decoded Quantum Interferometry (DQI), a recently proposed quantum algorithm for approximate optimization. We argue that DQI is hard to classically simulate, and that the hardness comes from locating an exponentially large hidden subset. This type of hardness is shared by Shor's algorithm, but the hidden subset here has no apparent group structure. We first prove that DQI can be simulated in a low level of the polynomial hierarchy, ruling out hardness arguments related to quantum supremacy. Instead, we show that DQI implements an existential coding theory bound based on the MacWilliams identity, and that it prepares a state within an obfuscated quantum harmonic oscillator. Both viewpoints require a coherent application of a discrete Hermite transform, which has no natural classical analog.
- Abstract（参考訳）: 最近提案された近似最適化のための量子アルゴリズムであるDecoded Quantum Interferometry (DQI) の複雑さについて検討した。
我々は、DQIは古典的にシミュレートするのが困難であり、その硬さは指数関数的に大きな隠れ部分集合を見つけることから生じると論じる。
この種の硬さはショアのアルゴリズムによって共有されるが、ここに隠された部分集合は明らかな群構造を持たない。
まず、DQIが多項式階層の低レベルにおいてシミュレート可能であることを証明し、量子超越性に関連する硬さの議論を除外する。
代わりに、DQI は MacWilliams の同一性に基づいて有界符号理論を実装し、難解な量子調和振動子内の状態を準備していることを示す。
どちらの視点も、自然古典的なアナログを持たない離散エルミート変換のコヒーレントな応用を必要とする。
関連論文リスト
- On the hardness of cloning and connections to representation theory [0.0]
隠れた部分空間上の最大絡み合った状態のクローニングアルゴリズムについて推測する。
予想と結果は、量子計算と表現論の間の関係から導かれる。
論文 参考訳（メタデータ） (2024-11-18T18:19:08Z) - 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) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - stateQIP = statePSPACE [0.15229257192293197]
本研究では,SDPPSPACEと状態QIPの2つの状態クラスの関係について検討する。
私たちの主な結果は、リバースインクルージョン、stateQIP $subseteq$ statePSPACEです。
また、一般的な量子対話プロトコルの最適証明戦略を量子空間で実装できることも示している。
論文 参考訳（メタデータ） (2023-01-18T19:00:17Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。