論文の概要: Solving k-SAT problems with generalized quantum measurement
- arxiv url: http://arxiv.org/abs/2406.13611v1
- Date: Wed, 19 Jun 2024 15:05:18 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-21 19:14:23.596469
- Title: Solving k-SAT problems with generalized quantum measurement
- Title（参考訳）: 一般化量子計測によるk-SAT問題の解法
- Authors: Yipei Zhang, Philippe Lewalle, K. Birgitta Whaley,
- Abstract要約: 我々は、ベンジャミン、ザオ、フィッツシモンズのプロジェクションに基づく量子測定駆動の$k$-SATアルゴリズムを任意の強度量子測定に一般化する。
このアルゴリズムは連続極限において時間と測定資源が有限であれば最も効率的であると主張する。
解ける$k$-SAT問題に対して、アルゴリズムによって生成されるダイナミクスは、長期(ゼノ)限界におけるターゲットダイナミクスに決定論的に収束する。
- 参考スコア（独自算出の注目度）: 0.7373617024876725
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We generalize the projection-based quantum measurement-driven $k$-SAT algorithm of Benjamin, Zhao, and Fitzsimons (BZF, arxiv:1711.02687) to arbitrary strength quantum measurements, including the limit of continuous monitoring. In doing so, we clarify that this algorithm is a particular case of the measurement-driven quantum control strategy elsewhere referred to as "Zeno dragging". We argue that the algorithm is most efficient with finite time and measurement resources in the continuum limit, where measurements have an infinitesimal strength and duration. Moreover, for solvable $k$-SAT problems, the dynamics generated by the algorithm converge deterministically towards target dynamics in the long-time (Zeno) limit, implying that the algorithm can successfully operate autonomously via Lindblad dissipation, without detection. We subsequently study both the conditional and unconditional dynamics of the algorithm implemented via generalized measurements, quantifying the advantages of detection for heralding errors. These strategies are investigated first in a computationally-trivial $2$-qubit $2$-SAT problem to build intuition, and then we consider the scaling of the algorithm on $3$-SAT problems encoded with $4 - 10$ qubits. The average number of shots needed to obtain a solution scales with qubit number as $\lambda^n$. For vanishing dragging time (with final readout only), we find $\lambda = 2$ (corresponding to a brute-force search over possible solutions). However, the deterministic (autonomous) property of the algorithm in the adiabatic (Zeno) limit implies that we can drive $\lambda$ arbitrarily close to $1$, at the cost of a growing pre-factor. We numerically investigate the tradeoffs in these scalings with respect to algorithmic runtime and assess their implications for using this analog measurement-driven approach to quantum computing in practice.
- Abstract（参考訳）: 我々は、ベンジャミン、ザオ、フィッツシモンズ(BZF, arxiv:1711.02687)のプロジェクションに基づく量子測定駆動の$k$-SATアルゴリズムを、連続的なモニタリングの限界を含む任意の強度量子測定に一般化する。
そこで我々は,このアルゴリズムが「ゼノ・ドラッギング(Zeno dragging)」と呼ばれる測定駆動型量子制御戦略の特別な場合であることを明らかにした。
このアルゴリズムは、無限小の強度と持続時間を持つ連続極限において、有限時間と測定資源で最も効率的であると主張する。
さらに、解答可能な$k$-SAT問題に対しては、アルゴリズムが生成したダイナミクスは、長期(Zeno)限界におけるターゲットダイナミクスに決定論的に収束し、検出することなくリンドブラッド散逸による自律的な動作が可能であることを示唆する。
その後、一般化された測定によって実装されたアルゴリズムの条件力学と非条件動力学の両方を研究し、誤り検出の利点を定量化する。
これらの戦略は、まず直観を構築するために計算的に自明な2$-qubitの2$-SAT問題において検討され、次に4〜10$-qubitで符号化された3$-SAT問題に対するアルゴリズムのスケーリングを検討する。
解を得るのに必要なショットの平均数は、キュービット数$\lambda^n$でスケールする。
ドラッグアウト時間(最終読み出しのみ)をなくすには、$\lambda = 2$(可能なソリューションに対するブルートフォース検索に対応する)を見つけます。
しかし、Adiabatic (Zeno) の極限におけるアルゴリズムの決定論的(自律的な)性質は、成長するプレファクターのコストで、$\lambda$を任意に$$$$$$にすることができることを意味している。
本稿では,これらのスケーリングにおけるアルゴリズム実行時のトレードオフを数値的に検討し,このアナログ計測駆動のアプローチを実際に量子コンピューティングに適用する上での意義を評価する。
関連論文リスト
- 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) - Quantum Algorithms for the Pathwise Lasso [1.8058773918890538]
古典的LARS(Least Angle Regression)パスワイズアルゴリズムに基づく新しい量子高次元線形回帰アルゴリズムを提案する。
我々の量子アルゴリズムは、ペナルティ項が変化するにつれて、完全な正規化パスを提供するが、特定の条件下では、イテレーション毎に2次的に高速である。
我々は、KKT条件の近似バージョンと双対性ギャップにより、LARSアルゴリズムがエラーに対して堅牢であることを証明した。
論文 参考訳（メタデータ） (2023-12-21T18:57:54Z) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳（メタデータ） (2023-12-18T18:29:01Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - An adaptive Bayesian quantum algorithm for phase estimation [0.0]
平均絶対誤差と平均二乗誤差の最適2次スケーリングを実現するためのコヒーレンスに基づく位相推定アルゴリズムを提案する。
ノイズの存在下で、我々のアルゴリズムは理論的な下界に近づく誤差を生成する。
論文 参考訳（メタデータ） (2023-03-02T19:00:01Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Private Frequency Estimation via Projective Geometry [47.112770141205864]
そこで本研究では,局所微分型(LDP)周波数推定のための新しいアルゴリズムであるProjectiveGeometryResponse (PGR)を提案する。
私たちの$varepsilon$-LDPアルゴリズムは、プライベートコイン設定で$lceillogkrceilビット、パブリックコイン設定で$varepsilonlog e + O(1)$の通信コストを持っています。
実際に使用される多くのパラメータ設定では、これは最近のPIによって達成されるO(n+k2)$Optimalコストよりも大幅に改善されている。
論文 参考訳（メタデータ） (2022-03-01T02:49:55Z) - Low depth algorithms for quantum amplitude estimation [6.148105657815341]
振幅推定のための2つの新しい低深さアルゴリズムの設計と解析
これらのアルゴリズムはモンテカルロ法の量子スピードアップを実現に近づける。
論文 参考訳（メタデータ） (2020-12-06T18:39:20Z) - More Practical and Adaptive Algorithms for Online Quantum State Learning [11.836183463815653]
本稿では,量子状態のオンライン学習を促進するアルゴリズムを開発する。
まず,Tallis-2エントロピーを用いた正規化Follow-the-Leader (RFTL) 法により,完全な後方視でO(sqrtMT)$の総損失が得られることを示す。
次に,古典的な調整学習率スケジュールに基づくパラメータフリーアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-01T15:17:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。