論文の概要: Variational learning algorithms for quantum query complexity
- arxiv url: http://arxiv.org/abs/2205.07449v3
- Date: Sat, 24 Feb 2024 14:01:03 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-28 01:05:59.925965
- Title: Variational learning algorithms for quantum query complexity
- Title（参考訳）: 量子クエリ複雑性のための変分学習アルゴリズム
- Authors: Zipeng Wu, Shi-Yao Hou, Chao Zhang, Lvzhou Li and Bei Zeng
- Abstract要約: 量子クエリの複雑さを研究するための変分学習アルゴリズムを開発した。
量子クエリの複雑さの様々なケースを解析するために,本手法を適用した。
本手法は,NISQ(Noisy Intermediate-Scale Quantum)デバイス上で容易に実装できる。
- 参考スコア（独自算出の注目度）: 3.980076328494117
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum query complexity plays an important role in studying quantum
algorithms, which captures the most known quantum algorithms, such as search
and period finding. A query algorithm applies $U_tO_x\cdots U_1O_xU_0$ to some
input state, where $O_x$ is the oracle dependent on some input variable $x$,
and $U_i$s are unitary operations that are independent of $x$, followed by some
measurements for readout. In this work, we develop variational learning
algorithms to study quantum query complexity, by formulating $U_i$s as
parameterized quantum circuits and introducing a loss function that is directly
given by the error probability of the query algorithm. We apply our method to
analyze various cases of quantum query complexity, including a new algorithm
solving the Hamming modulo problem with $4$ queries for the case of $5$-bit
modulo $5$, answering an open question raised in arXiv:2112.14682, and the
result is further confirmed by a Semidefinite Programming (SDP) algorithm.
Compared with the SDP algorithm, our method can be readily implemented on the
near-term Noisy Intermediate-Scale Quantum (NISQ) devices and is more flexible
to be adapted to other cases such as the fractional query models.
- Abstract（参考訳）: 量子クエリの複雑さは、探索や周期探索などの既知の量子アルゴリズムをキャプチャする量子アルゴリズムの研究において重要な役割を果たす。
クエリアルゴリズムは、ある入力状態に$U_tO_x\cdots U_1O_xU_0$を適用し、$O_x$は入力変数の$x$に依存したオラクルであり、$U_i$sは$x$に依存しないユニタリ演算であり、次に読み出しのためのいくつかの測定を行う。
本研究では、パラメータ化量子回路として$U_i$sを定式化し、クエリアルゴリズムの誤差確率から直接与えられる損失関数を導入することにより、量子クエリの複雑さを研究する変分学習アルゴリズムを開発する。
提案手法を応用して,ハミングモジュロ問題を5ドル(約5,500円)で解くアルゴリズムや,arXiv:2112.14682で提起されたオープンな質問に答えるアルゴリズムなど,量子クエリ複雑性のケースを解析し,さらにセミデフィニティプログラミング(SDP)アルゴリズムで検証する。
SDPアルゴリズムと比較すると,本手法は近距離雑音中規模量子(NISQ)デバイスで容易に実装でき,分数クエリモデルなどの他のケースにも適応できる。
関連論文リスト
- The Power of Adaptivity in Quantum Query Algorithms [0.5702169790677977]
問合せモデルにおける深度計算のトレードオフについて検討し、その深さは適応的な問合せラウンドの数と1ラウンド当たりの並列クエリ数に対応する。
我々は、量子アルゴリズム間の最も強力な分離を$r$対$r-1$の適応性を持つラウンドで達成する。
論文 参考訳（メタデータ） (2023-11-27T18:21:32Z) - Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - On the exact quantum query complexity of $\text{MOD}_m^n$ and
$\text{EXACT}_{k,l}^n$ [0.0]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。
我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文 参考訳（メタデータ） (2023-03-20T08:17:32Z) - $T$-depth-optimized Quantum Search with Quantum Data-access Machine [0.0]
量子データアクセスマシン(QDAM)と呼ばれる効率的な量子データアクセスプロセスを導入する。
我々は,実効量子誤り訂正符号内の論理量子ビットからなるフォールトトレラント量子計算(FTQC)の観点から,我々のアルゴリズムのランタイムを解析する。
論文 参考訳（メタデータ） (2022-11-08T01:36:02Z) - Time and Query Complexity Tradeoffs for the Dihedral Coset Problem [0.19731444261635428]
Z_N$のディヘドラルコセット問題(DCP)は量子コンピューティングやポスト量子暗号において広く研究されている。
Ettinger-Hoyerアルゴリズムは$O(log(N))$クエリでDCPを解くことが知られている。
本稿では,Ettinger-Hoyerアルゴリズムよりも線形クエリ方式を改良した最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-29T05:30:54Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Alternatives to a nonhomogeneous partial differential equation quantum
algorithm [52.77024349608834]
Apsi(textbfr)=f(textbfr)$ という形の非等質線型偏微分方程式を解くための量子アルゴリズムを提案する。
これらの成果により、現代の技術に基づく量子アルゴリズムの実験的実装が容易になった。
論文 参考訳（メタデータ） (2022-05-11T14:29:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。