論文の概要: A Quantum Algorithm For Computing Contextuality Bounds

• arxiv url: http://arxiv.org/abs/2509.20250v1
• Date: Wed, 24 Sep 2025 15:36:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-02 17:22:45.457339
• Title: A Quantum Algorithm For Computing Contextuality Bounds
• Title（参考訳）: コンテキスト境界計算のための量子アルゴリズム
• Authors: Colm Kelleher, Frédéric Holweck,
• Abstract要約: 我々はGroverの探索アルゴリズムに基づく量子アルゴリズムを提供し、古典的なブルート力法よりも高速な$O(sqrtn loglogn)$$$$O(sqrtn loglogn)$O(sqrtn loglogn)$O(n$)$O(sqrtn loglogn)$の文脈性を計算する。 また,基本状態の位相に関連情報をエンコードし,回路幅と深度要件を低減させるGroverのバリエーションについても検討した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum contextuality is a limitation on deterministic hidden variable models, testable in measurement scenarios where outcomes differ under quantum or classical descriptions due to a common set of constraints. When considering measurements of $N$-qubit spin operators, constraints arise from commutation relations and classical bounds are determined by the $\textit{degree}$ of contextuality, an NP-hard quantity to compute in general, related to the larger class of optimisation problems known as $\texttt{MaxLin2}$. In this work we give a quantum algorithm based on Grover's search algorithm, computing the degree of contextuality in $O(\sqrt{n} \log\log{n})$ in $n$ states, a speedup over classical brute force method. We also study variations of Grover which encode the relevant information in the phases of the basis states, reducing circuit width and depth requirements with indicative complexity of $O(n^{\frac{1}{3}}(\log{n})^{2}\log\log{n})$. Testing on contemporary quantum backends with the IBM quantum experience gives inconclusive outputs due to noise-induced errors, an issue hopefully fixed by future hardware.
• Abstract（参考訳）: 量子文脈性 (quantum contextuality) は、決定論的隠れ変数モデルに対する制限であり、量子的または古典的な記述の下で結果が異なるような測定シナリオで検証可能である。 N$-量子スピン作用素の測度を考えると、可換関係から制約が生じ、古典的境界は、一般に計算するNPハード量である$\textt{degree}$によって決定され、より大きい最適化問題のクラスである$\texttt{MaxLin2}$に関連付けられる。 本研究では,Groverの探索アルゴリズムに基づく量子アルゴリズムを提案し,$O(\sqrt{n} \log\log{n})$の文脈性を計算する。 また、基本状態の相における関連情報を符号化し、回路幅と深さ要件を$O(n^{\frac{1}{3}}(\log{n})^{2}\log\log{n})$の表示複雑性で減少させるGroverのバリエーションについても検討する。 現代の量子バックエンドをIBMの量子体験でテストすると、ノイズによるエラーによる不確定な出力が得られる。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still Impractical, Quantum Distributed Algorithms [0.0]
  確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。 従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。 Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
  論文  参考訳（メタデータ） (2023-04-06T02:18:52Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Deterministic and Entanglement-Efficient Preparation of Amplitude-Encoded Quantum Registers [0.533024001730262]
  古典ベクトル $mathbfb$ は量子状態の振幅で符号化される。 任意の状態の$Q$ qubitsは通常、約2Q$のエンタングゲートを必要とする。 状態準備に必要な量子資源を柔軟に削減できる決定論的(非変分法)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-10-26T07:37:54Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。 我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。 我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-14T11:05:26Z)

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

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