論文の概要: Quantum-Classical Tradeoffs in the Random Oracle Model
- arxiv url: http://arxiv.org/abs/2211.12954v1
- Date: Wed, 23 Nov 2022 13:55:28 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-19 01:31:15.601430
- Title: Quantum-Classical Tradeoffs in the Random Oracle Model
- Title（参考訳）: ランダムOracleモデルにおける量子古典的トレードオフ
- Authors: Yassine Hamoudi, Qipeng Liu, Makrand Sinha
- Abstract要約: 我々はこのハイブリッドフレームワークを,古典的なクエリ記録方法と圧縮されたZhandryを補間して,クエリ記録を行うハイブリッドフレームワークと呼んでいる。
探索のための最適衝突探索の簡易な証明と,クエリ探索のための最適トレードオフを示すことで,その適用性を示す。
- 参考スコア（独自算出の注目度）: 2.294014185517203
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study tradeoffs between quantum and classical queries for hybrid
algorithms that have black-box access to a random oracle. Although there are
several established techniques for proving query lower bounds for both quantum
and classical algorithms, there is no such widely applicable technique for
hybrid algorithms and the optimal tradeoffs for many fundamental problems are
still unknown $\unicode{x2013}$ an optimal tradeoff for the search problem was
only shown recently by Rosmanis, although not in the random oracle model. For
another fundamental problem, collision finding, the optimal tradeoff was not
known.
In this work, we develop a framework for recording a query transcript for
quantum-classical algorithms that represents the knowledge gained by the
algorithm. The main feature of this framework is to allow us to record queries
in two incompatible bases $\unicode{x2013}$ classical queries in the standard
basis and quantum queries in the Fourier basis $\unicode{x2013}$ in a
consistent way. We call the framework the hybrid compressed oracle as it
naturally interpolates between the classical way of recording queries and the
compressed oracle framework of Zhandry for recording quantum queries. We
demonstrate its applicability by giving a simpler proof of the optimal
quantum-classical tradeoff for search and by showing an optimal tradeoff for
collision finding.
- Abstract（参考訳）: ランダムなオラクルへのブラックボックスアクセスを持つハイブリッドアルゴリズムに対する量子クエリと古典クエリのトレードオフについて検討する。
量子アルゴリズムと古典アルゴリズムの両方のクエリローバウンドを証明するための確立された技法はいくつかあるが、ハイブリッドアルゴリズムにはそのような広く適用可能な技法はなく、多くの基本的な問題に対する最適なトレードオフはまだ未知の$\unicode{x2013}$ 探索問題の最適トレードオフはロスマニスによって最近発表されたが、ランダムなオラクルモデルでは示されていない。
もう一つの根本的な問題である衝突発見では、最適トレードオフは分かっていなかった。
本研究では,このアルゴリズムが獲得した知識を表す量子古典的アルゴリズムの問合せ記録のためのフレームワークを開発する。
このフレームワークの主な特徴は、標準ベースで$\unicode{x2013}$古典的なクエリと、Fourierベースで$\unicode{x2013}$の量子クエリを一貫性のある方法で記録できるようにすることである。
我々はこのフレームワークをハイブリッド圧縮オラクルと呼び、古典的なクエリ記録方法とZhandryの圧縮オラクルフレームワークを自然に補間して量子クエリを記録する。
探索の最適量子古典的トレードオフのより簡単な証明を与え,衝突発見の最適トレードオフを示すことにより,その適用性を示す。
関連論文リスト
- A quantum-classical hybrid algorithm with Ising model for the learning with errors problem [13.06030390635216]
本稿では,Ising Model (HAWI) を用いた量子古典ハイブリッドアルゴリズムを提案し,LWE問題に対処する。
我々は、ハミルトンの低エネルギーレベルを同定して解を抽出し、現在のノイズの多い中間スケール量子(NISQ)デバイスの実装に適したものにする。
我々のアルゴリズムは反復であり、その時間複雑性はハミルトンの低エネルギーレベルを見つけるために使われる特定の量子アルゴリズムに依存する。
論文 参考訳（メタデータ） (2024-08-15T05:11:35Z) - Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
現在利用可能な量子デバイスは、限られた量子ビットと高いレベルのノイズしか持たず、それらのデバイスで正確に解決できる問題のサイズを制限している。
我々は、変分量子アルゴリズム -- 離散化量子排他探索 -- を改善する新しい方法を提案する。
論文 参考訳（メタデータ） (2024-07-24T22:06:05Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Limitations of Noisy Quantum Devices in Computational and Entangling
Power [5.178527492542246]
回路深さが$O(log n)$以上のノイズ量子デバイスは、いかなる量子アルゴリズムにも利点がないことを示す。
また、ノイズ量子デバイスが1次元および2次元の量子ビット接続の下で生成できる最大エンタングルメントについても検討する。
論文 参考訳（メタデータ） (2023-06-05T12:29:55Z) - Making the cut: two methods for breaking down a quantum algorithm [0.0]
現在、ノイズの多い小規模量子ハードウェアの時代において、計算上の優位性に達する可能性のある量子アルゴリズムを見つけることは、依然として大きな課題である。
我々は、量子アルゴリズムを低い(クエリ)深さのラウンドに分解する2つの方法を特定し、特徴付ける。
最初の問題では並列化が最高のパフォーマンスを提供するのに対し、2番目はより良い選択であることを示す。
論文 参考訳（メタデータ） (2023-05-17T18:00:06Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Iterative Qubits Management for Quantum Index Searching in a Hybrid
System [56.39703478198019]
IQuCSは、量子古典ハイブリッドシステムにおけるインデックス検索とカウントを目的としている。
我々はQiskitでIQuCSを実装し、集中的な実験を行う。
その結果、量子ビットの消費を最大66.2%削減できることが示されている。
論文 参考訳（メタデータ） (2022-09-22T21:54:28Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Hardware Efficient Quantum Search Algorithm [17.74233101199813]
本稿では,この課題を克服するために,ハードウェアの効率的な量子探索アルゴリズムを提案する。
我々の鍵となる考え方は、グローバル拡散操作を低コストな局所拡散に置き換えることである。
回路コストの削減は、システムの成功率を著しく向上させる。
論文 参考訳（メタデータ） (2021-03-26T01:08:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。