論文の概要: 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} の一般化を通じてブール多項式系の解を抽出する新しい手法を提案する。
関連論文リスト
- Polynomial-depth quantum algorithm for computing matrix determinant [49.494595696663524]
正方行列の行列式を計算するアルゴリズムを提案し,それを実現する量子回路を構築する。
行列の各行は、ある量子系の純粋な状態として符号化される。
したがって、認められた行列はこれらの系の量子状態の正規化まで任意である。
論文 参考訳(メタデータ) (2024-01-29T23:23:27Z) - Preconditioning for a Variational Quantum Linear Solver [0.0]
必要なアンザッツ深さの顕著な減少を数値的に示すことにより,プリコンディショニングが量子アルゴリズムにも有用であることを明らかにする。
この回路深さの低減は、ノイズ中間スケール量子(NISQ)アルゴリズムの効率と精度を向上させる鍵となる。
論文 参考訳(メタデータ) (2023-12-25T08:50:22Z) - A fixed-point algorithm for matrix projections with applications in
quantum information [7.988085110283119]
このアルゴリズムは反復数において最適解に指数関数的に収束することを示す。
量子資源理論および量子シャノン理論における我々のアルゴリズムのいくつかの応用について論じる。
論文 参考訳(メタデータ) (2023-12-22T11:16:11Z) - 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) - Depth analysis of variational quantum algorithms for heat equation [0.0]
量子コンピュータ上での熱方程式を解くための3つの方法を考える。
ハミルトン分解におけるパウリ積の指数的な数は、量子速度を達成できない。
アンザッツ・ツリーのアプローチは行列の明示的な形式を利用しており、古典的アルゴリズムよりも有利である。
論文 参考訳(メタデータ) (2022-12-23T14:46:33Z) - 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-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳(メタデータ) (2020-11-09T01:13:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。