論文の概要: Limitations of the Macaulay matrix approach for using the HHL algorithm
to solve multivariate polynomial systems
- arxiv url: http://arxiv.org/abs/2111.00405v2
- Date: Fri, 21 Jul 2023 20:32:59 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-26 01:30:45.603643
- 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とGaociteChenGaoaruはBooleanシステム解決のための新しい量子アルゴリズムを提案した。
多くの場合(すべてではないとしても)、Groverベースの網羅的探索アルゴリズムは一般化よりも優れていることを示す。
- 参考スコア(独自算出の注目度): 3.789692994119356
- License: http://creativecommons.org/licenses/by/4.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
$\mathbb{C}$, 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 $\mathbb{C}$ 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
$\mathbb{F}_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} はブール多項式系の解法のための新しい量子アルゴリズムを提案した。
彼らのアプローチの鍵となる考え方は、ブール多項式系から派生した$\mathbb{C}$上のマカオレー線型系に量子線形系(QLS)アルゴリズムを適用することである。
アルゴリズムの効率は、マコーレー行列の条件数に依存する。
本稿では,ブール解のハミング重みの関数として条件数に強い下限を与え,多くの(すべてではないにせよ)グロバーに基づく排他的探索アルゴリズムがアルゴリズムを上回ることを示す。
そこで,Chen と Gao のアルゴリズムを改良し,ブール・マコーレー線形系を$\mathbb{C}$ 上に導入し,元のマコーレー線形系を減らした。
この改良されたアルゴリズムは、溶液のハミング重みがブール変数の数で対数である場合、ブルト力アルゴリズムを著しく上回る可能性がある。
さらに,Valiant-Vaziraniアフィンハッシュ法を用いて,改良アルゴリズムの正しさを簡易かつ基礎的に証明するとともに,Chen,Gao,Yuan \cite{ChenGao2018} によるその後の研究を改良した$\mathbb{F}_q$以上の多項式系に拡張する。
また,量子クーポンコレクタ問題 \cite{arunachalam2020quantumcouponcollector} の一般化を通じてブール多項式系の解を抽出する新しい手法を提案する。
関連論文リスト
- An Efficient Quantum Algorithm for Linear System Problem in Tensor Format [4.264200809234798]
本稿では,最近のアディバティック・インスパイアされたQLSAの進歩に基づく量子アルゴリズムを提案する。
実装の全体的な複雑さは、その次元において多対数的であることを厳密に示します。
論文 参考訳(メタデータ) (2024-03-28T20:37:32Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。