論文の概要: Quantum Search with In-Place Queries
- arxiv url: http://arxiv.org/abs/2504.03620v1
- Date: Fri, 04 Apr 2025 17:37:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-14 15:47:44.55564
- Title: Quantum Search with In-Place Queries
- Title（参考訳）: ページ内クエリによる量子検索
- Authors: Blake Holman, Ronak Ramachandran, Justin Yirka,
- Abstract要約: 我々は$O(sqrtN)$ in-placeクエリを用いた置換変換のための量子アルゴリズムを設計する。
そこで本研究では,XORクエリをインプレースクエリよりも少なくする問題があることを述べる。
- 参考スコア（独自算出の注目度）: 1.1999555634662633
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum query complexity is typically characterized in terms of XOR queries |x,y> to |x,y+f(x)> or phase queries, which ensure that even queries to non-invertible functions are unitary. When querying a permutation, another natural model is unitary: in-place queries |x> to |f(x)>. Some problems are known to require exponentially fewer in-place queries than XOR queries, but no separation has been shown in the opposite direction. A candidate for such a separation was the problem of inverting a permutation over N elements. This task, equivalent to unstructured search in the context of permutations, is solvable with $O(\sqrt{N})$ XOR queries but was conjectured to require $\Omega(N)$ in-place queries. We refute this conjecture by designing a quantum algorithm for Permutation Inversion using $O(\sqrt{N})$ in-place queries. Our algorithm achieves the same speedup as Grover's algorithm despite the inability to efficiently uncompute queries or perform straightforward oracle-controlled reflections. Nonetheless, we show that there are indeed problems which require fewer XOR queries than in-place queries. We introduce a subspace-conversion problem called Function Erasure that requires 1 XOR query and $\Theta(\sqrt{N})$ in-place queries. Then, we build on a recent extension of the quantum adversary method to characterize exact conditions for a decision problem to exhibit such a separation, and we propose a candidate problem.
- Abstract（参考訳）: 量子クエリの複雑性は通常、XORクエリ |x,y> から |x,y+f(x)> またはフェーズクエリによって特徴づけられる。
置換を問うとき、別の自然なモデルはユニタリである: in-place query |x> to |f(x)>。
いくつかの問題は、XORクエリよりも指数関数的に少ないインプレースクエリを必要とすることが知られているが、反対方向には分離が示されていない。
そのような分離の候補は、N元上の置換を反転させる問題であった。
このタスクは置換の文脈における非構造化探索と等価であり、$O(\sqrt{N})$ XORクエリで解けるが、$Omega(N)$ in-placeクエリを必要とすると推測された。
我々は、$O(\sqrt{N})$ in-placeクエリを使って、置換反転の量子アルゴリズムを設計することで、この予想に反論する。
提案アルゴリズムは,クエリを効率よく非計算したり,直接オラクル制御されたリフレクションを行うことができないにもかかわらず,Groverのアルゴリズムと同じ高速化を実現する。
それにもかかわらず、XORクエリをインプレースクエリよりも少なくする問題があることが示される。
1つのXORクエリと$\Theta(\sqrt{N})$ in-placeクエリを必要とするサブスペース変換問題であるFunction Erasureを導入する。
そこで, 量子対位法を拡張して, 決定問題に対する厳密な条件を特徴付ける手法を構築し, 候補問題を提案する。
関連論文リスト
- Clustering with Non-adaptive Subset Queries [16.662507957069813]
クエリ $S の部分集合 U$, $|S|=2$ が与えられたとき、オラクルは、ポイントが同じクラスタにあり、そうでなければ、イエスを返す。
ペアワイズクエリを用いた適応アルゴリズムでは、必要なクエリの数は$Theta(nk)$であることが知られている。
非適応スキームは$Omega(n2)$クエリを必要とするが、これは全ての点を問合せすることで得られる自明な$O(n2)$上限と一致する。
論文 参考訳（メタデータ） (2024-09-17T05:56:07Z) - Quantum Query-Space Lower Bounds Using Branching Programs [0.18416014644193066]
GQBPの制限されたバージョンに対する、最初の明示的なクエリ空間の低いバウンダリを示す。
次に、問題を一般化して、ハミング距離が一定である2つの弦の間を決定するために、同じ境界が成り立つことを示す。
我々の結果は、任意の非コンスタント対称ブール関数の問合せ複雑性に基づく$Omega(sqrtn)$-lower境界の代替証明を生成する。
論文 参考訳（メタデータ） (2024-07-09T13:58:53Z) - Accelerated quantum search using partial oracles and Grover's algorithm [0.0]
グロバーのアルゴリズム(英: Grover's algorithm)は、順序のないデータベースを探索する手段として考案されたアルゴリズムであり、量子計算によって生成される結果集合から解を抽出するためにも用いられる。
マッチング条件の各ビットに個別のオラクルを関連付け、独立にテスト可能な複数の部分的なオラクル関数を得るという考え方を探求する。
アルゴリズムは最も単純な検索シナリオに対して検証され、入力されたインデックスビットは置換演算を用いてスクランブルされる。
論文 参考訳（メタデータ） (2024-03-19T11:32:02Z) - On the Two-sided Permutation Inversion Problem [45.69327512339002]
オラクルが量子クエリーを、置換の前方方向と逆方向の両方に許容する設定について検討する。
逆問題の結果の変動の硬さを結合するいくつかの定理を証明した。
以上の結果から,逆数に対する逆数アクセスが与えられると,逆数問題はかなり難しくなる可能性が示唆された。
論文 参考訳（メタデータ） (2023-06-23T18:31:48Z) - Private Query Release via the Johnson-Lindenstrauss Transform [93.20051580730234]
差分プライバシーを持つ統計的クエリに対する回答を解放する新しい手法を提案する。
鍵となる考え方は、クエリの回答を低次元空間にランダムに投影することである。
単純なノイズ付加機構を用いて予測されたクエリに回答し、元の次元まで答えを引き上げます。
論文 参考訳（メタデータ） (2022-08-15T19:19:16Z) - Variational learning algorithms for quantum query complexity [3.980076328494117]
量子クエリの複雑さを研究するための変分学習アルゴリズムを開発した。
量子クエリの複雑さの様々なケースを解析するために,本手法を適用した。
本手法は,NISQ(Noisy Intermediate-Scale Quantum)デバイス上で容易に実装できる。
論文 参考訳（メタデータ） (2022-05-16T05:16:15Z) - Query2Particles: Knowledge Graph Reasoning with Particle Embeddings [49.64006979045662]
本稿では,知識グラフにエッジを欠いた複雑な論理的クエリに応答するクエリ埋め込み手法を提案する。
回答エンティティは、エンティティの埋め込みとクエリの埋め込みの類似性に応じて選択される。
埋め込み空間上の様々な領域から多様な回答を検索するために,複雑なKGクエリ応答方法Q2Pを提案する。
論文 参考訳（メタデータ） (2022-04-27T11:16:08Z) - Quantum search-to-decision reductions and the state synthesis problem [0.4248594146171025]
量子アルゴリズムは古典的な決定オラクルにクエリを行い、所望の量子状態を出力することを示す。
また、逆精度まで$mathsfQMA$問題の証人を生成する量子時間アルゴリズムが存在することも示している。
また、より一般的な$textitstate合成問題$を探索し、ターゲット状態の効率的な合成を目標とする。
論文 参考訳（メタデータ） (2021-11-04T16:52:58Z) - Fuzzy Clustering with Similarity Queries [56.96625809888241]
ファジィ(fuzzy, soft objective)は、よく知られた$k$-means問題の一般化である。
クエリを少なくすることで、問題の解決が容易になる。
論文 参考訳（メタデータ） (2021-06-04T02:32:26Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - The Sparse Vector Technique, Revisited [67.57692396665915]
我々は、微分プライバシーの文献において最も基礎的で広く適用可能なテクニックの1つを再考する。
この単純なアルゴリズムは、データベース上のあるクエリの値が、私たちが期待している値に近いかどうかをプライベートにテストします。
一つの個人が過剰なクエリの回答に寄与しない限り、クエリのテストを継続できる代替の、等しくシンプルなアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-10-02T10:50:52Z) - Query2box: Reasoning over Knowledge Graphs in Vector Space using Box
Embeddings [84.0206612938464]
query2boxは、不完全な知識グラフ上の任意のクエリを推論するための埋め込みベースのフレームワークである。
query2boxは、スケーラブルな方法で$wedge$, $vee$, $exists$で任意の論理クエリを処理可能であることを示す。
本稿では,3つの大規模KGに対するQuery2boxの有効性を示すとともに,クエリ2boxが技術状況に対して最大25%の相対的な改善を達成可能であることを示す。
論文 参考訳（メタデータ） (2020-02-14T11:20:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。