論文の概要: Quantum algorithm for Valiant-Vazirani reduction

• arxiv url: http://arxiv.org/abs/2606.18428v1
• Date: Tue, 16 Jun 2026 19:22:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-24 16:10:14.701091
• Title: Quantum algorithm for Valiant-Vazirani reduction
• Title（参考訳）: Valiant-Vazirani還元のための量子アルゴリズム
• Authors: Patrick Kelly, Victoria S. Ordonez, Michael R. Geller,
• Abstract要約: ヴァリアント・ヴァジラーニの定理のフィルタによる実装を構築し、SATからSATへのランダムな時間短縮を実現する。 雑音自由限界において、SAT問題はねじれ非線形性を用いてねじれ時間で解くことができる。 非線形量子コプロセッサ結合のねじれに対するフォールトトレラントな実装は、sf NP(#sf P)問題に対する時間解を可能にする。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: There is growing interest in extensions of the standard model of gate-based quantum computation to include auxiliary degrees of freedom evolving according to a nonlinear Schrödinger equation. By reducing the Boolean satisfiability problem SAT to quantum state discrimination, Abrams and Lloyd argued that the right type of nonlinearity can be used to solve {\sf NP} and \#{\sf P} problems in polynomial time, at least in an idealized noise-free limit. For practical implementation, however, we are restricted to simulated and emergent nonlinearities, such as that appearing in mean field models for ultracold atoms and similar ensembles. A prominent example is the torsion model, which arises in two-component Bose-Einstein condensates and spin models with all-to-all Ising interaction. But torsion-based state discrimination appears to fall short of solving SAT. Here we close this gap by constructing the filtered oracle of the Valiant-Vazirani theorem, providing a randomized polynomial-time reduction from SAT to UNIQUE SAT, a promise problem where there is at most 1 satisfying assignment. In the noise free limit, the UNIQUE SAT problem can be olved in polynomial time using torsion nonlinearity. Quantum Valiant-Vazirani reduction is no faster than the efficient classical version, but a fault-tolerant implementation coupled to a nonlinear quantum coprocessor simulating torsion would enable polynomial time solution to {\sf NP} (but not \#{\sf P}) problems.
• Abstract（参考訳）: 非線形シュレーディンガー方程式に従って進化する補助的な自由度を含むゲートベースの量子計算の標準モデルの拡張への関心が高まっている。 ブール整合性問題SATを量子状態判別に還元することで、エイブラムスとロイドは、多項式時間において、少なくとも理想化された雑音のない極限において、正しいタイプの非線形性は {\sf NP} と \#{\sf P} の問題を解くのに使用できると主張した。 しかし、実際の実装では、超低温原子の平均場モデルや類似のアンサンブルに現れるような、シミュレーションおよび創発的非線形性に制限される。 顕著な例はトーションモデルであり、2成分のボース=アインシュタイン凝縮と全てのイジング相互作用を持つスピンモデルに現れる。 しかし、トーションに基づく国家差別はSATの解決に足りていないようだ。 ここでは、ヴァリアント・ヴァジラニの定理のフィルターされたオラクルを構築し、SAT から UNIQUE SAT へのランダムな多項式時間還元を与えることにより、このギャップを埋める。 雑音自由極限において、UNIQUE SAT問題はねじれ非線形性を用いて多項式時間で解くことができる。 量子バリアント・ヴァジラニ還元は、効率的な古典版よりも速くはないが、ねじれをシミュレートする非線形量子コプロセッサと結合したフォールトトレラント実装は、多項式時間解を {\sf NP}(ただし \#{\sf P} ではない)の問題を実現できる。

関連論文リスト

• Operator-Algebraic Methods for Asymptotic-Preserving Quantum Simulation of Open Systems [0.0]
  我々は,量子計算資源を用いたマルチスケール物理システムのシミュレーションを行うための,数学的に厳密なフレームワークを開発した。 自然アナログ進化や解析多様体射影による高速な緩和を実現する層状量子プロトコルがダイヤモンドノルムに一様に収束することを証明する。 この研究は、古典的マルチスケール数値解析と量子シミュレーションアルゴリズムの間に、原理化された数学的ブリッジを提供する。
  論文  参考訳（メタデータ） (2026-05-16T19:27:58Z)
• A Residual-Based Quantum Linear System Algorithm with Dynamic Stopping and Applications to Elliptic PDEs [3.3636842548621275]
  量子線形システムアルゴリズム(QLSA)は、厳密な最悪のケースの複雑性を保証するが、そのランタイムは事前に仮定されたスペクトル情報から選択されることが多い。 ほとんどのQLSAは、古典的なものと異なり、特定のインスタンスがすでに収束しているかどうかを知らせる組み込みメカニズムを提供していません。 本研究では,残差を持つ拡張力学系を設計し,残差レジスタの測定によりオンザフライ収束インジケータが提供される。
  論文  参考訳（メタデータ） (2026-05-07T15:22:55Z)
• Sparse QUBO Formulation for Efficient Embedding via Network-Based Decomposition of Equality and Inequality Constraints [0.35331503620315147]
  等式制約と不等式制約に対して,かなりスペーサーな論理QUBOモデルを構築する手法を提案する。 特定のネットワーク構造に基づいて補助変数を追加することにより、本手法は元の制約をより小さく、より管理しやすい制約に分解する。 D-Waveのハードウェア上での実験結果から,我々の定式化は埋め込みに必要な量子ビット数を大幅に削減することを示した。
  論文  参考訳（メタデータ） (2026-01-26T03:40:06Z)
• Non-commutative optimization problems with differential constraints [0.0]
  非可換最適化(NPO)問題は、一部の演算子のクエンチの状態平均を最小化する。 作用素変数の部分集合が通常の微分方程式の系を満たすような NPO 問題の変種を考える。 作用素有界性の穏やかな条件下では、そのようなすべての問題に対して、同じ解で標準 NPO 問題を構築することができる。
  論文  参考訳（メタデータ） (2024-08-05T15:46:57Z)
• Quantum and classical algorithms for nonlinear unitary dynamics [0.5729426778193399]
  我々は$fracd|urangledtという形の非線形微分方程式に対する量子アルゴリズムを提案する。 また,Euler法に基づく古典的アルゴリズムを導入し,制限された場合の量子アルゴリズムへのコンパラブルなスケーリングを実現する。
  論文  参考訳（メタデータ） (2024-07-10T14:08:58Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  量子計算の2つのモデル: CQ_dとQC_d。 CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。 CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
  論文  参考訳（メタデータ） (2022-01-06T03:10:53Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)

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

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