論文の概要: Optimal exact quantum algorithm for the promised element distinctness
problem
- arxiv url: http://arxiv.org/abs/2211.05443v1
- Date: Thu, 10 Nov 2022 09:33:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-19 19:43:48.446182
- Title: Optimal exact quantum algorithm for the promised element distinctness
problem
- Title（参考訳）: 期待される要素識別問題に対する最適完全量子アルゴリズム
- Authors: Guanzhong Li and Lvzhou Li
- Abstract要約: 要素差分問題は、文字列$x=(x_1,ldots,x_N)$の$N$要素が同じ値の2つの要素を含むかどうかを決定することである。
保証問題に対する厳密な量子アルゴリズムを提案するが、これにはO(N2/3)$クエリが必要である。
- 参考スコア（独自算出の注目度）: 0.2741266294612775
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The element distinctness problem is to determine whether a string
$x=(x_1,\ldots,x_N)$ of $N$ elements contains two elements of the same value
(a.k.a colliding pair), for which Ambainis proposed an optimal quantum
algorithm. The idea behind Ambainis' algorithm is to first reduce the problem
to the promised version in which $x$ is promised to contain at most one
colliding pair, and then design an algorithm $\mathcal{A}$ requiring
$O(N^{2/3})$ queries based on quantum walk search for the promise problem.
However, $\mathcal{A}$ is probabilistic and may fail to give the right answer.
We thus, in this work, design an exact quantum algorithm for the promise
problem which never errs and requires $O(N^{2/3})$ queries. This algorithm is
proved optimal. Technically, we modify the quantum walk search operator on
quasi-Johnson graph to have arbitrary phases, and then use Jordan's lemma as
the analyzing tool to reduce the quantum walk search operator to the
generalized Grover's operator. This allows us to utilize the recently proposed
fixed-axis-rotation (FXR) method for exact quantum search, and hence achieve
100\% success.
- Abstract（参考訳）: 要素差分問題は、文字列$x=(x_1,\ldots,x_N)$の$N$要素が同じ値の2つの要素(例えば衝突対)を含むかどうかを判断することであり、アンバイニスは最適量子アルゴリズムを提案した。
ambainisのアルゴリズムの背後にあるアイデアは、最初に、x$が少なくとも1つの衝突ペアを含むと約束されたバージョンに問題を縮小し、その後、promise問題の量子ウォーク検索に基づいて$o(n^{2/3})$クエリを必要とする$\mathcal{a}$というアルゴリズムを設計することである。
しかし、$\mathcal{a}$ は確率的であり、正しい答えを与えることができない。
したがって、本研究では、errが無く、$o(n^{2/3})$クエリを必要とするpromise問題の正確な量子アルゴリズムを設計する。
このアルゴリズムは最適である。
理論的には、擬ジョンソングラフ上の量子ウォーク探索演算子を任意の位相を持つように修正し、ヨルダンの補題を解析ツールとして、一般化されたグローバー作用素に量子ウォーク探索演算子を還元する。
これにより、最近提案された固定軸回転法(FXR)を正確な量子探索に利用し、100\%の成功を達成できる。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Algoritmo de Contagem Qu\^antico Aplicado ao Grafo Bipartido Completo [0.0]
Groverのアルゴリズムは、$O(sqrtN/k)$ stepsを使って$N$要素を持つ、順序のないデータベースで$k$要素を見つけることができる。
この研究は、他のグラフのマーク要素の値$k$を推定するために量子カウントアルゴリズムを使用する問題に取り組む。
論文 参考訳（メタデータ） (2023-12-05T21:15:09Z) - 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) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Efficient quantum algorithms for solving quantum linear system problems [0.0]
拡張行列 $C$ の特異値 0 の右特異ベクトルを求める問題を解くための2つの量子アルゴリズムを提案する。
どちらのアルゴリズムも$kappa $の最適なクエリ複雑性を満たす。
論文 参考訳（メタデータ） (2022-08-14T02:49:26Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Finding many Collisions via Reusable Quantum Walks [1.376408511310322]
衝突発見は暗号解析におけるユビキタスな問題である。
本稿では,この問題に対するアルゴリズムを改良し,特に許容可能なパラメータの範囲を広げる。
応用として、最短ベクトル問題に対する量子シービングアルゴリズムを改善する。
論文 参考訳（メタデータ） (2022-05-27T14:50:45Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。