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

• arxiv url: http://arxiv.org/abs/2606.18428v2
• Date: Mon, 22 Jun 2026 21:05:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-25 07:14:09.179654
• Title: Quantum algorithm for Valiant-Vazirani reduction
• Title（参考訳）: Valiant-Vazirani還元のための量子アルゴリズム
• Abstract要約: SATを量子状態判別に還元することで、アブラムスとロイドはNPと#Pの問題を解くのに正しいタイプの非線形性を用いることができると主張した。 ここではヴァリアント・ヴァジラニの定理を構築し、超フィルター付きノイズフリー極限問題を解くためにSATからSATへの無作為時間還元を与える。
• 参考スコア（独自算出の注目度）: 0.014582793306013616
• 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 NP and #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 solved 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 NP (but not #P) problems.
• Abstract（参考訳）: 非線形シュレーディンガー方程式に従って進化する補助的な自由度を含むゲートベースの量子計算の標準モデルの拡張への関心が高まっている。 ブール整合性問題SATを量子状態判別に還元することにより、アブラムスとロイドは、少なくとも理想化された雑音のない極限において、多項式時間でNPと#Pの問題を解くのに正しいタイプの非線形性を用いることができると主張した。 しかし、実際の実装では、超低温原子の平均場モデルや類似のアンサンブルに現れるような、シミュレーションおよび創発的非線形性に制限される。 顕著な例はトーションモデルであり、2成分のボース=アインシュタイン凝縮と全てのイジング相互作用を持つスピンモデルに現れる。 しかし、トーションに基づく国家差別はSATの解決に足りていないようだ。 ここでは、ヴァリアント・ヴァジラニの定理のフィルターされたオラクルを構築し、SAT から UNIQUE SAT へのランダムな多項式時間還元を与えることにより、このギャップを埋める。 雑音のない極限において、UNIQUE SAT問題はねじれ非線形性を用いて多項式時間で解くことができる。 量子バリアント・ヴァジラニ還元は、効率的な古典版よりも高速ではないが、ねじれをシミュレートする非線形量子コプロセッサと結合したフォールトトレラント実装は、NP(#P)問題に対する多項式時間解を可能にする。

関連論文リスト

• Wavelength-Uniform Quantum Algorithms for Quantum Dynamics [39.740772144144366]
  具体的には、空間的次元が複雑であり、小さな波長の負のパワーを伴わずに離散化して有界化することにより、空間的格子が周波数を解けなくても正しい物理観測可能を捉えることができ、したがってナイキスト・シャノンサンプリング定理を無視することができる。
  論文  参考訳（メタデータ） (2026-09-07T12:00:04Z)
• Constrained minimax approximation for quantum signal processing [1.2825618016709242]
  量子信号処理(QSP)は、量子回路を用いて変換を実装するためのシンプルで効率的なフレームワークを提供する。 その古典的な設計段階は、制約付き近似問題(英語版)をもたらす: ミニマックスパリティ(英語版)(minimax parity)は、適合集合上で一様にターゲット関数を近似し、領域$[0,1]$で一等に有界なままである。 離散化は問題を線形プログラムに変換するが、有限個のサンプリングされた点の集合における実現性は、領域全体の実現性を保証するものではない。 アクティブセット制約強制と組み合わされたRemez交換法は、多くのテストインスタンスにおいて効率的であるが、安定性はターゲットに依存している。
  論文  参考訳（メタデータ） (2026-08-31T15:10:52Z)
• 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)
• Variational Adiabatic Gauge Transformation on real quantum hardware for effective low-energy Hamiltonians and accurate diagonalization [68.8204255655161]
  変分アダバティックゲージ変換(VAGT)を導入する。 VAGTは、現在の量子コンピュータを用いてユニタリ回路の変動パラメータを学習できる非摂動型ハイブリッド量子アルゴリズムである。 VAGTの精度は、RigettiおよびIonQ量子コンピュータ上でのシミュレーションと同様に、トラフ数値シミュレーションで検証される。
  論文  参考訳（メタデータ） (2021-11-16T20:50:08Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。 本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。 提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
  論文  参考訳（メタデータ） (2021-07-08T17:59:55Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)

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

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