論文の概要: 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)
• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  変分量子アルゴリズムは、現在の量子計算のデファクトモデルとなっている。 そのような問題の1つは、ある文字列の特定のビットを見つけることで構成される非構造化探索である。 我々は、CTQWを用いてQAOA配列を復元し、最近のトロッター公式の理論の進歩を利用して、クエリの複雑さを束縛する。
  論文  参考訳（メタデータ） (2024-03-22T18:00:03Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Learning the Complexity of Weakly Noisy Quantum States [0.5662299435213419]
  ターゲット量子状態の古典的シャドウ表現を利用して、弱雑音量子状態の回路複雑性を予測する。 本研究は,学習アルゴリズムと量子状態複雑性の橋渡しを行い,量子状態の固有特性を特徴付ける学習アルゴリズムのパワーを強調した。
  論文  参考訳（メタデータ） (2023-03-31T06:02:44Z)
• 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)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  古典的AES様対称暗号のための変分量子攻撃アルゴリズム(VQAA)を提案する。 VQAAでは、既知の暗号文は、正規グラフを通して構築されるハミルトンの基底状態として符号化される。
  論文  参考訳（メタデータ） (2022-05-07T03:15:15Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。 我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。 任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
  論文  参考訳（メタデータ） (2022-03-30T02:02:16Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。