論文の概要: 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)
• Non-Linear Transformations of Quantum Amplitudes: Exponential Improvement, Generalization, and Applications [0.0]
  量子アルゴリズムは量子状態の振幅を操作して計算問題の解を求める。 量子状態の振幅に非線形関数の一般クラスを適用するための枠組みを提案する。 我々の研究は、最適化、状態準備、量子化学、機械学習といった分野において、潜在的に多くの応用が可能な重要かつ効率的なビルディングブロックを提供する。
  論文  参考訳（メタデータ） (2023-09-18T14:57:21Z)
• 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)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications [10.436969366019015]
  我々は、$Theta(n)$-depth回路は、$O(ndlog d)$ acillary qubitsを持つ$Theta(log(nd))で作成可能であることを示す。 我々は、ハミルトンシミュレーション、方程式の線形系解法、量子ランダムアクセスメモリの実現など、異なる量子コンピューティングタスクにおける結果の適用について論じる。
  論文  参考訳（メタデータ） (2022-01-27T13:16:30Z)
• Deterministic and Entanglement-Efficient Preparation of Amplitude-Encoded Quantum Registers [0.533024001730262]
  古典ベクトル $mathbfb$ は量子状態の振幅で符号化される。 任意の状態の$Q$ qubitsは通常、約2Q$のエンタングゲートを必要とする。 状態準備に必要な量子資源を柔軟に削減できる決定論的(非変分法)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-10-26T07:37:54Z)
• Topological obstructions to quantum computation with unitary oracles [0.0]
  いくつかのタスクは量子回路では不可能であるが、古典的なバージョンはクローン化などが容易である。 プロセストモグラフィ、オラクル中立化、$sqrt[dim U]U$、$UT$、$Udagger$アルゴリズムの制限を示す。 その結果、線形光学の利点を強化し、緩和因果性の実験に挑戦し、多くのアウトカム測定で新しいアルゴリズムを動機づけた。
  論文  参考訳（メタデータ） (2020-11-19T18:52:38Z)
• 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)

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

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