論文の概要: Limitations of the Macaulay matrix approach for using the HHL algorithm
to solve multivariate polynomial systems
- arxiv url: http://arxiv.org/abs/2111.00405v1
- Date: Sun, 31 Oct 2021 04:13:15 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-09 19:06:43.411589
- Title: Limitations of the Macaulay matrix approach for using the HHL algorithm
to solve multivariate polynomial systems
- Title（参考訳）: hhlアルゴリズムを用いた多変量多項式系の解法に対するマコーレー行列法の適用限界
- Authors: Jintai Ding, Vlad Gheorghiu, Andr\'as Gily\'en, Sean Hallgren,
Jianqiang Li
- Abstract要約: 先日、ChenとGaociteChenGao 2017はBooleanシステム解決のための新しい量子アルゴリズムを提案した。
本稿では,Chen と Gao のアルゴリズムよりも検索アルゴリズムの方が優れていることを示す。
また,Valiant-Vaziraniアフィンハッシュ法を用いて,改良アルゴリズムの精度を簡易かつ基礎的に証明する。
- 参考スコア（独自算出の注目度）: 3.789692994119356
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently Chen and Gao~\cite{ChenGao2017} proposed a new quantum algorithm for
Boolean polynomial system solving, motivated by the cryptanalysis of some
post-quantum cryptosystems. The key idea of their approach is to apply a
Quantum Linear System (QLS) algorithm to a Macaulay linear system over $\CC$,
which is derived from the Boolean polynomial system. The efficiency of their
algorithm depends on the condition number of the Macaulay matrix. In this
paper, we give a strong lower bound on the condition number as a function of
the Hamming weight of the Boolean solution, and show that in many (if not all)
cases a Grover-based exhaustive search algorithm outperforms their algorithm.
Then, we improve upon Chen and Gao's algorithm by introducing the Boolean
Macaulay linear system over $\CC$ by reducing the original Macaulay linear
system. This improved algorithm could potentially significantly outperform the
brute-force algorithm, when the Hamming weight of the solution is logarithmic
in the number of Boolean variables.
Furthermore, we provide a simple and more elementary proof of correctness for
our improved algorithm using a reduction employing the Valiant-Vazirani affine
hashing method, and also extend the result to polynomial systems over $\FF_q$
improving on subsequent work by Chen, Gao and Yuan \cite{ChenGao2018}. We also
suggest a new approach for extracting the solution of the Boolean polynomial
system via a generalization of the quantum coupon collector problem
\cite{arunachalam2020QuantumCouponCollector}.
- Abstract（参考訳）: 最近、Chen and Gao~\cite{ChenGao2017} はブール多項式系の解法のための新しい量子アルゴリズムを提案した。
彼らのアプローチの鍵となるアイデアは、量子線形系(QLS)アルゴリズムを、ブール多項式系から派生した$\CC$上のマコーレー線形系に適用することである。
アルゴリズムの効率は、マコーレー行列の条件数に依存する。
本稿では,ブール解のハミング重みの関数として条件数に強い下限を与え,多くの(すべてではないにせよ)グロバーに基づく排他的探索アルゴリズムがアルゴリズムを上回ることを示す。
そこで,Chen と Gao のアルゴリズムを改良して Boolean Macaulay 線形系を$\CC$ 以上で導入し,元の Macaulay 線形系を削減した。
この改良されたアルゴリズムは、溶液のハミング重みがブール変数の数で対数である場合、ブルト力アルゴリズムを著しく上回る可能性がある。
さらに,Valiant-Vaziraniアフィンハッシュ法を用いて,改良アルゴリズムの精度を簡易かつ基礎的に証明し,Chen,Gao,Yuan \cite{ChenGao2018} によるその後の研究を改良した$\FF_q$以上の多項式系に拡張する。
また,量子クーポンコレクタ問題 \cite{arunachalam2020quantumcouponcollector} の一般化を通じてブール多項式系の解を抽出する新しい手法を提案する。
関連論文リスト
- A quantum algorithm for advection-diffusion equation by a probabilistic imaginary-time evolution operator [0.0]
本稿では, 線形対流拡散方程式を, 新しい近似確率的想像時間進化(PITE)演算子を用いて解く量子アルゴリズムを提案する。
我々は, 対流拡散方程式から得られるハミルトニアンの想像時間進化を実現するために, 明示的な量子回路を構築した。
我々のアルゴリズムは、Harrow-Hassidim-Lloyd (HHL)アルゴリズムに匹敵する結果を与える。
論文 参考訳（メタデータ） (2024-09-27T08:56:21Z) - Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。
本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
論文 参考訳（メタデータ） (2024-09-06T03:32:02Z) - A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm [9.804179673817574]
古典的近位点法(PPA)に着想を得た量子線形系問題(QLSP)に対する新しい量子アルゴリズムを提案する。
提案手法は,既存のtexttimattQLSP_solverを経由した修正行列の逆変換が可能なメタアルゴリズムとみなすことができる。
ステップサイズ$eta$を慎重に選択することにより、提案アルゴリズムは線形システムに対して、以前のアプローチの適用性を阻害する条件数への依存を軽減するために、効果的に事前条件を定めることができる。
論文 参考訳（メタデータ） (2024-06-19T23:15:35Z) - An Improved Method for Quantum Matrix Multiplication [0.0]
線形方程式を解くための有望な量子アルゴリズムに従えば、指数関数的に精度に依存した線形方程式系を解くためのアプローチを提供する。
この応用を動機づけるいくつかの例を含め、この改良された行列応用アルゴリズムを効率の良い量子プロシージャで明示的に適用することをさらに議論する。
論文 参考訳（メタデータ） (2023-11-23T15:00:36Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - Hybrid quantum-classical and quantum-inspired classical algorithms for
solving banded circulant linear systems [0.8192907805418583]
帯状循環系に対する量子状態の組み合わせの凸最適化に基づく効率的なアルゴリズムを提案する。
帯状循環行列を巡回置換に分解することにより, 量子状態の組み合わせによる近似解を$K$とする。
我々は,従来のシミュレーションと実際のIBM量子コンピュータ実装を用いて本手法を検証し,熱伝達などの物理問題への適用性を示した。
論文 参考訳（メタデータ） (2023-09-20T16:27:16Z) - 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) - Alternatives to a nonhomogeneous partial differential equation quantum
algorithm [52.77024349608834]
Apsi(textbfr)=f(textbfr)$ という形の非等質線型偏微分方程式を解くための量子アルゴリズムを提案する。
これらの成果により、現代の技術に基づく量子アルゴリズムの実験的実装が容易になった。
論文 参考訳（メタデータ） (2022-05-11T14:29:39Z) - Polynomial unconstrained binary optimisation inspired by optical
simulation [52.11703556419582]
制約のないバイナリ最適化の問題を解決するために,光コヒーレントIsingマシンにヒントを得たアルゴリズムを提案する。
提案アルゴリズムを既存のPUBOアルゴリズムに対してベンチマークし,その優れた性能を観察する。
タンパク質の折り畳み問題や量子化学問題へのアルゴリズムの適用は、PUBO問題による電子構造問題の近似の欠点に光を当てる。
論文 参考訳（メタデータ） (2021-06-24T16:39:31Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳（メタデータ） (2020-11-09T01:13:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。