論文の概要: Nonlinear Hamiltonians and Boolean satisfiability
- arxiv url: http://arxiv.org/abs/2605.14822v1
- Date: Thu, 14 May 2026 13:32:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-15 21:45:34.843714
- Title: Nonlinear Hamiltonians and Boolean satisfiability
- Title（参考訳）: 非線形ハミルトニアンとブール充足性
- Authors: Michael R. Geller, Victoria S. Ordonez, Yohannes Abate,
- Abstract要約: スケーラブルなフォールトトレラント量子コンピュータを1つ以上のアンシラ量子ビットに結合する量子計算の拡張モデルを考える。
ここでは、異なるハミルトニアンによって生成される3種類の状態判別器について考察する。
- 参考スコア（独自算出の注目度）: 0.01593065406609169
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider an extended model of quantum computation where a scalable fault-tolerant quantum computer is coupled to one or more ancilla qubits that evolve according to a nonlinear Schrödinger equation. Following the approach of Abrams and Lloyd, an efficient quantum circuit evaluating an $n$-bit Boolean function in conjunctive normal form is used to prepare an ancilla encoding its number $s$ of satisfying assignments ($0 \le s \le 2^n$). This is followed by a nonlinear quantum state discrimination gate on the ancilla qubit that is used to learn properties of $s$. Here we consider three types of state discriminators generated by different nonlinear Hamiltonians. First, given a restricted Boolean satisfiability problem with the promise of at most one satisfying assignment ($ 0 \le s \le 1$), we show that a qubit with $\langle σ^z \rangle σ^z$ nonlinearity can be used to efficiently determine whether $s = 0$ or $s = 1$, solving the UNIQUE SAT problem. Here $\langle A \rangle := \langle ψ| A |ψ\rangle $ denotes expectation in the current state. UNIQUE SAT is NP-hard under a randomized polynomial-time reduction (of course any discussion of complexity assumes a scalable, fault-tolerant implementation). Second, for unrestricted satisfiability problems with $ 0 \le s \le 2^n$, a Hamiltonian with $ \langle σ^x \rangle σ^y - \langle σ^y \rangle σ^x$ nonlinearity can be used to efficiently determine whether $s=0$ or $s>0$, thereby solving 3SAT, which is NP-complete. Finally, we show that $ \langle σ^y \rangle \langle σ^z \rangle σ^x - \langle σ^x \rangle \langle σ^z \rangle σ^y $ nonlinearity can be used to efficiently measure $s$ and solve #SAT, which is #P-complete. The nonlinear models are of mean field type and might be simulated with ultracold atoms.
- Abstract（参考訳）: 我々は、スケーラブルなフォールトトレラント量子コンピュータを非線形シュレーディンガー方程式に従って進化する1つ以上のアンシラ量子ビットに結合する量子計算の拡張モデルを考える。
Abrams と Lloyd のアプローチに従うと、結合正規形式で$n$-bit Boolean 関数を評価する効率的な量子回路が、その数$s$を満足する代入(0 \le s \le 2^n$)を符号化するアンシラを作成するために用いられる。
これに続いて、アンシラ量子ビット上の非線形量子状態判別ゲートが、$s$の性質を学習するために使用される。
ここでは、異なる非線形ハミルトニアンによって生成される3種類の状態判別器について考察する。
まず、制限されたブール充足可能性問題(0 \le s \le 1$)が与えられたとき、$\langle σ^z \rangle σ^z$非線形性を用いて、$s = 0$ か $s = 1$ を効率的に決定できることを示し、UNIQUE SAT 問題を解く。
ここで、$\langle A \rangle := \langle は現在の状態における期待を表す。
UNIQUE SAT はランダム化多項式時間短縮の下でNPハードである(もちろん複雑性に関する議論はスケーラブルでフォールトトレラントな実装を前提としている)。
第二に、0 \le s \le 2^n$ の非制限充足性問題に対して、$ \langle σ^x \rangle σ^y - \langle σ^y \rangle σ^x$ 非線形性は、$s=0$ か $s>0$ を効率的に決定するために用いられるので、NP完全である 3SAT を解くことができる。
最後に、$ \langle σ^y \rangle \langle σ^z \rangle σ^x - \langle σ^x \rangle σ^z \rangle σ^y $ 非線形性を用いて、$s$を効率的に測定し、#SATを解くことができる。
非線形モデルは平均場型であり、超低温原子でシミュレートされる。
関連論文リスト
- Simulation of Non-Hermitian Hamiltonians with Bivariate Quantum Signal Processing [0.0]
H_mathrmeff = H_R + iH_I$, where $H_R$ is Hermitian and $H_I succeq 0$。
論文 参考訳（メタデータ） (2026-05-12T17:40:56Z) - Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
乗算前の2つの行列のエントリーワイズスカラー量子化について検討した。
我々は、閉形式の最適点密度 [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X を求め、相関駆動相転移を証明した。
論文 参考訳（メタデータ） (2026-03-20T01:53:44Z) - Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。
どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文 参考訳（メタデータ） (2026-03-19T15:53:41Z) - Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Quantum oracles for the finite element method [45.200826131319815]
本研究では,N倍の剛性および質量行列のブロックエンコーディングに使用されるオラクルの実装に必要な量子ルーチンについて検討した。
本稿では, 要素幾何学, 平方根の計算, 条件演算の実装など, 必要なオラクルを構築する方法を示す。
論文 参考訳（メタデータ） (2025-04-28T14:28:31Z) - Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - A generic quantum Wielandt's inequality [0.9975341265604578]
一般に$k$は$mathcalO(n2)$の次数でなければならないと推測されている。
量子ウィーランドの不等式の一般的なバージョンを提供し、確率 1 で最適な長さを与える。
我々は、Projected Entangled Pair Stateの長年のオープンな問題に新たな光を当てた。
論文 参考訳（メタデータ） (2023-01-19T18:57:32Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
量子状態$psi$を標準で計算するためのアルゴリズムを,古典的に記述し,解析する。
我々のアルゴリズムはサンプリングタスクを$n$-qubit状態のポリ(n)$振幅の計算に還元する。
論文 参考訳（メタデータ） (2021-12-15T21:44:05Z) - The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
量子回路 $C$ on $n$ qubits とサンプル $z in 0,1n$ のとき、ベンチマークは$|langle z|C|0n rangle|2$ の計算を伴う。
任意の $varepsilon ge frac1mathrmpoly(n)$ に対して、サンプル $z$ を出力することは、平均で $|langle z|C|0nrangle|2$ に対して最適な 1-クエリであることを示す。
論文 参考訳（メタデータ） (2020-08-20T01:04:32Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。
格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。
NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
論文 参考訳（メタデータ） (2020-02-25T19:18:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。