論文の概要: Near-perfect Reachability of Variational Quantum Search with Depth-1
Ansatz
- arxiv url: http://arxiv.org/abs/2301.13224v1
- Date: Mon, 30 Jan 2023 19:00:07 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-01 18:55:39.115872
- Title: Near-perfect Reachability of Variational Quantum Search with Depth-1
Ansatz
- Title（参考訳）: Depth-1 Ansatzを用いた変分量子探索のほぼ完全到達性
- Authors: Junpeng Zhan
- Abstract要約: グローバーの探索アルゴリズムは、科学的な問題を解く際の劇的なスピードアップで有名である。
最近提案された変分量子探索(VQS)アルゴリズムは、最大26キュービットのGroverアルゴリズムよりも指数関数的な優位性を示している。
ここでは,Groverのアルゴリズムが要求する指数関数的に深い回路をマルチ制御NOTゲートに置き換えることができることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Grover's search algorithm is renowned for its dramatic speedup in solving
many important scientific problems. The recently proposed Variational Quantum
Search (VQS) algorithm has shown an exponential advantage over Grover's
algorithm for up to 26 qubits. However, its advantage for larger numbers of
qubits has not yet been proven. Here we show that the exponentially deep
circuit required by Grover's algorithm can be replaced by a multi-controlled
NOT gate together with either a single layer of Ry gates or two layers of
circuits consisting of Hadamard and NOT gates, which is valid for any number of
qubits greater than five. We prove that the VQS, with a single layer of Ry
gates as its Ansatz, has near-perfect reachability in finding the good element
of an arbitrarily large unstructured data set, and its reachability
exponentially improves with the number of qubits, where the reachability is
defined to quantify the ability of a given Ansatz to generate an optimal
quantum state. Numerical studies further validate the excellent reachability of
the VQS. Proving the near-perfect reachability of the VQS, with a depth-1
Ansatz, for any number of qubits completes an essential step in proving its
exponential advantage over Grover's algorithm for any number of qubits, and the
latter proving is significant as it means that the VQS can efficiently solve
NP-complete problems.
- Abstract（参考訳）: グローバーの探索アルゴリズムは、多くの重要な科学的問題を解決する際の劇的なスピードアップで有名である。
最近提案された変分量子探索(VQS)アルゴリズムは、最大26キュービットのGroverアルゴリズムよりも指数関数的な優位性を示している。
しかし、より多くの量子ビットに対する利点はまだ証明されていない。
ここでは,Groverのアルゴリズムで要求される指数関数的に深い回路を,Ryゲートの1層,あるいはHadamardとNOTゲートの2層のいずれかで複数制御されたNOTゲートに置き換えることができることを示す。
我々は、ryゲートの単一層をアンサッツとして持つvqsが、任意に大きい非構造化データセットのよい要素を見つけるのにほぼ完全な到達可能性を持つことを証明し、到達可能性が与えられたアンサッツの量子状態を生成する能力を定量化するために到達可能性を定義する量子ビット数によって指数関数的に向上することを示す。
数値的研究は、VQSの優れた到達性をさらに検証する。
深さ1アンザッツで任意の量子ビットに対してVQSのほぼ完全な到達性を証明することは、任意の数の量子ビットに対してグロバーのアルゴリズムよりも指数関数的な優位性を証明するための重要なステップである。
関連論文リスト
- Distributed Exact Generalized Grover's Algorithm [9.675088142486729]
本稿では,汎用探索問題の解法として,分散Exactized Grover's Algorithm (DEGGA)を提案する。
我々のアルゴリズムは、目標状態が100%$の理論的確率で精度を保証します。
我々の方法は合計$n$ qubitsを必要とし、補助的なqubitsは不要である。
論文 参考訳（メタデータ） (2024-05-11T09:17:11Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
量子コンピューティングは、アルゴリズムを設計する新しい方法の基礎となる。
どの場の量子スピードアップが達成できるかという新たな課題が生じる。
量子サブルーチンの設計は、従来のサブルーチンよりも効率的で、新しい強力な量子アルゴリズムに固い柱を向ける。
論文 参考訳（メタデータ） (2024-02-26T09:32:07Z) - Utilizing Novel Quantum Counters for Grover's Algorithm to Solve the
Dominating Set Problem [0.0]
グロバーのアルゴリズムは、量子コンピュータ上で実行されるよく知られた非構造量子探索アルゴリズムである。
本稿では、Groverのアルゴリズムのオラクルを構成するために、3つの優れた性質を持つ新しい量子カウンタを利用する。
論文 参考訳（メタデータ） (2023-12-14T23:00:35Z) - Variational Quantum Search with Shallow Depth for Unstructured Database
Search [0.0]
変分量子探索(VQS)は、変分量子アルゴリズムとパラメータ化量子回路に基づく新しいアルゴリズムである。
深さ10アンザッツは、$n$+1量子ビットで表される2n$要素のうち、$k$の総確率を増幅できることを示す。
我々は,VQSの深さ56回路がGroverのアルゴリズムの深さ270,989回路を置き換えることを実証した。
論文 参考訳（メタデータ） (2022-12-16T17:16:54Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Quantum Speedup for Higher-Order Unconstrained Binary Optimization and
MIMO Maximum Likelihood Detection [2.5272389610447856]
実数値の高次非制約二項最適化問題をサポートする量子アルゴリズムを提案する。
提案アルゴリズムは,古典的領域におけるクエリの複雑さを低減し,量子領域における2次高速化を実現する。
論文 参考訳（メタデータ） (2022-05-31T00:14:49Z) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。
我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。
任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
論文 参考訳（メタデータ） (2022-03-30T02:02:16Z) - Efficiently Solve the Max-cut Problem via a Quantum Qubit Rotation
Algorithm [7.581898299650999]
我々はQQRA(Quantum Qubit Rotation Algorithm)という単純なアルゴリズムを導入する。
最大カット問題の近似解は 1 に近い確率で得られる。
我々は、よく知られた量子近似最適化アルゴリズムと古典的なゲーマン・ウィリアムソンアルゴリズムと比較する。
論文 参考訳（メタデータ） (2021-10-15T11:19:48Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
本研究では,トラベリングセールスマン問題に必要なキュービット数を大幅に削減できることを示す。
また、量子ビット効率と回路深さ効率のモデルを円滑に補間する符号化方式を提案する。
論文 参考訳（メタデータ） (2020-09-15T18:17:27Z) - Improving the Performance of Deep Quantum Optimization Algorithms with
Continuous Gate Sets [47.00474212574662]
変分量子アルゴリズムは計算的に難しい問題を解くのに有望であると考えられている。
本稿では,QAOAの回路深度依存性能について実験的に検討する。
この結果から, 連続ゲートセットの使用は, 短期量子コンピュータの影響を拡大する上で重要な要素である可能性が示唆された。
論文 参考訳（メタデータ） (2020-05-11T17:20:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。