論文の概要: Oracle problems as communication tasks and optimization of quantum algorithms
- arxiv url: http://arxiv.org/abs/2409.15549v1
- Date: Mon, 23 Sep 2024 21:03:39 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-26 12:23:42.002982
- Title: Oracle problems as communication tasks and optimization of quantum algorithms
- Title（参考訳）: 量子アルゴリズムの通信タスクと最適化におけるOracleの問題
- Authors: Amit Te'eni, Zohar Schwartzman-Nowik, Marcin Nowakowski, Paweł Horodecki, Eliahu Cohen,
- Abstract要約: 鍵となる疑問は、アルゴリズムが一定の数のクエリのみを使用して学習タスクをどの程度うまく成功させることができるかである。
本研究では,出力と実値の相互情報を用いたアルゴリズムの性能測定を提案する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum query complexity mainly studies the number of queries needed to learn some property of a black box with high probability. A closely related question is how well an algorithm can succeed with this learning task using only a fixed number of queries. In this work, we propose measuring an algorithm's performance using the mutual information between the output and the actual value. A key observation is that if an algorithm is only allowed to make a single query and the goal is to optimize this mutual information, then we obtain a task which is similar to a basic task of quantum communication, where one attempts to maximize the mutual information of the sender and receiver. We make this analogy precise by formally considering the oracle as a separate subsystem, whose state records the unknown oracle identity. The oracle query prepares a state, which is then measured; and the target property of the oracle plays the role of a message that should be deduced from the measurement outcome. Thus we obtain a link between the optimal single-query algorithm and minimization of the extent of quantum correlations between the oracle and the computer subsystems. We also find a lower bound on this mutual information, which is related to quantum coherence. These results extend to multiple-query non-adaptive algorithms. As a result, we gain insight into the task of finding the optimal non-adaptive algorithm that uses at most a fixed number of queries, for any oracle problem.
- Abstract（参考訳）: 量子クエリの複雑性は主に、高い確率でブラックボックスの特性を学習するために必要なクエリの数を研究する。
密接に関連する疑問は、アルゴリズムが一定数のクエリのみを使用して、この学習タスクをどの程度うまく成功させることができるかである。
本研究では,出力と実値の相互情報を用いたアルゴリズムの性能測定を提案する。
鍵となる観察は、アルゴリズムが単一のクエリのみを許容し、目的がこの相互情報を最適化するならば、送信者と受信者の相互情報の最大化を試みる量子通信の基本課題に類似したタスクが得られます。
我々は、この類似性を、その状態が未知のオラクルのアイデンティティを記録している独立したサブシステムとして、公式には託宣を考慮し、正確にする。
オラクルクエリは、次に測定された状態を準備し、オラクルのターゲットプロパティは、測定結果から導出されるべきメッセージの役割を担います。
したがって、最適な単一クエリアルゴリズムと、オラクルとコンピュータサブシステムの間の量子相関の度合いの最小化のリンクを得る。
また、量子コヒーレンスに関連するこの相互情報の低い境界も見出す。
これらの結果は、多重クエリ非適応アルゴリズムにまで拡張される。
その結果、任意のオラクル問題に対して、少なくとも1つの固定数のクエリを使用する最適な非適応アルゴリズムを見つけるという課題について、洞察を得ることができた。
関連論文リスト
- Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。
評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
論文 参考訳（メタデータ） (2023-10-26T18:23:21Z) - Quantum Search Approaches to Sampling-Based Motion Planning [0.0]
本稿では,従来のサンプリング型モーションプランナを,量子探索アルゴリズムを用いて解くことのできるデータベース・オーラル構造として,新しい定式化を提案する。
より単純なスパース環境では、量子完全経路探索アルゴリズム (Quantum Full Path Search Algorithm, Q-FPS) を定式化し、完全なランダムパス解の重ね合わせを生成する。
密集した非構造環境において、親子接続の量子重ね合わせを生成する量子高速探索ランダムツリーアルゴリズム q-RRT を定式化する。
論文 参考訳（メタデータ） (2023-04-10T19:12:25Z) - Automatic Generation of an Efficient Less-Than Oracle for Quantum
Amplitude Amplification [0.4374837991804085]
グローバーのアルゴリズムは量子コンピューティングへのよく知られた貢献である。
本稿では、振幅増幅のための位相標示オラクルを構築する古典的アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-13T13:52:19Z) - Quantum algorithm for finding minimum values in a Quantum Random Access
Memory [0.0]
最適古典的決定論的アルゴリズムは、データベース内の要素数と線形に増加する時間複雑性で最小値を見つけることができる。
本稿では,データベースの最小値を求める量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-12T16:22:17Z) - A quantum algorithm to estimate the closeness to the Strict Avalanche
criterion in Boolean functions [4.392337343771302]
与えられたブール関数の近さを厳密な雪崩基準を満たすもの(SAC)に推定する量子アルゴリズムを提案する。
このアルゴリズムはBoolean関数のoracleの$n$クエリを必要とし、$n$は入力変数の数である。
このアルゴリズムは、SACを量子オラクルへの最も少ない呼び出しで検証し、与えられた信頼境界に対して最も少ないサンプルを必要とすることを示す。
論文 参考訳（メタデータ） (2022-11-25T12:32:01Z) - Efficient algorithms for quantum information bottleneck [64.67104066707309]
本稿では,情報ボトルネックの量子一般化のための新しい一般アルゴリズムを提案する。
本アルゴリズムは, 先行結果と比較して, 収束の速度と定性に優れる。
特に、量子システムは、量子情報のボトルネックに関して、同じ大きさの古典的なシステムよりも厳格に優れた性能を達成できることがわかった。
論文 参考訳（メタデータ） (2022-08-22T14:20:05Z) - On Efficient Approximate Queries over Machine Learning Models [30.26180913049285]
本稿では,プロキシを活用し,オラクルの使用量を最小限に抑えることで,クエリ応答を近似する新しい統一フレームワークを開発する。
我々のフレームワークは、データサンプルに高価なオラクルを呼び出し、DB内のオブジェクトに安価なプロキシを適用するという、司法的な組み合わせを使用します。
我々のアルゴリズムは最先端のアルゴリズムより優れており、証明可能な統計的保証で高い結果が得られる。
論文 参考訳（メタデータ） (2022-06-06T18:35:19Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Resource Optimisation of Coherently Controlled Quantum Computations with
the PBS-calculus [55.2480439325792]
量子計算のコヒーレント制御は、いくつかの量子プロトコルやアルゴリズムを改善するために使用できる。
我々は、量子光学にインスパイアされたコヒーレント制御のためのグラフィカル言語PBS計算を洗練する。
論文 参考訳（メタデータ） (2022-02-10T18:59:52Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - New Oracle-Efficient Algorithms for Private Synthetic Data Release [52.33506193761153]
微分プライベートな合成データを構築するための3つの新しいアルゴリズムを提案する。
アルゴリズムは最悪の場合でも差分プライバシーを満たす。
現状の手法である高次元行列機構 citeMcKennaMHM18 と比較すると,我々のアルゴリズムは大規模作業負荷の精度が向上する。
論文 参考訳（メタデータ） (2020-07-10T15:46:05Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。