論文の概要: Oracle problems as communication tasks and optimization of quantum algorithms
- arxiv url: http://arxiv.org/abs/2409.15549v2
- Date: Tue, 13 May 2025 12:28:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-14 20:57:54.162059
- 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 studies the number of queries needed to learn some property of a black box. 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. The task of optimizing this mutual information using a single query, 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 splitting the algorithm between two agents, obtaining a communication protocol. The oracle's target property plays the role of a message that Alice encodes into a quantum state, which is subsequently sent over to Bob. The first part of the algorithm performs this encoding, and the second part measures the state and aims to deduce the message from the outcome. Moreover, we formally consider the oracle as a separate subsystem, whose state records the unknown oracle identity. Within this construction, Bob's optimal measurement basis minimizes the quantum correlations between the two subsystems. We also find a lower bound on the mutual information, which is related to quantum coherence. These results extend to multiple-query algorithms. As a result, we describe the optimal non-adaptive algorithm that uses at most a fixed number of queries, for any oracle classification problem. We demonstrate our results by studying several well-known algorithms through the proposed framework.
- Abstract（参考訳）: 量子クエリ複雑性は、ブラックボックスのいくつかの特性を学ぶのに必要なクエリの数を研究する。
密接に関連する疑問は、アルゴリズムが一定数のクエリだけでこの学習タスクをどれだけうまく成功させることができるかである。
本研究では,出力と実値の相互情報を用いたアルゴリズムの性能測定を提案する。
この相互情報を単一のクエリで最適化するタスクは、送信者と受信者の相互情報の最大化を試みる量子通信の基本タスクと似ている。
アルゴリズムを2つのエージェントに分割し、通信プロトコルを取得することにより、この類似性を正確にする。
オラクルの標的特性はアリスが量子状態にエンコードするメッセージの役割を担い、後にボブに渡される。
アルゴリズムの第1部はこれを符号化し、第2部は状態を測定し、結果からメッセージを引き出す。
さらに、私たちは、このオラクルを、その状態が未知のオラクルのアイデンティティを記録している独立したサブシステムと公式にみなす。
この構成の中で、ボブの最適測定基底は、2つのサブシステム間の量子相関を最小化する。
また、量子コヒーレンスに関連する相互情報の低い境界も見出す。
これらの結果はマルチクエリアルゴリズムにまで拡張される。
その結果,任意のオラクル分類問題に対して,少なくとも一定数のクエリを使用する最適非適応アルゴリズムについて述べる。
提案するフレームワークを用いて,いくつかのよく知られたアルゴリズムを研究した結果を実証する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。