論文の概要: Quantum mechanics can find a needle in a haystack every time
- arxiv url: http://arxiv.org/abs/2506.06435v1
- Date: Fri, 06 Jun 2025 18:00:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-10 16:33:10.272745
- Title: Quantum mechanics can find a needle in a haystack every time
- Title（参考訳）: 量子力学は毎回干し草の山に針を見つけることができる
- Authors: Fatemeh Mohit, Joshua Guanzon, Jaden McKinlay, Till J. Weinhold, Casey R. Myers, Marcelo P. Almeida, Markus Rambach, Andrew G. White,
- Abstract要約: グローバーのアルゴリズムは、量子コンピューティングの優位性の先駆的な実証の1つである。
4から10要素のデータベースを探索し、1つのマークされた要素を選択すれば、平均的な成功確率は99.77 pm 0.05%である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Grover's algorithm is one of the pioneering demonstrations of the advantages of quantum computing over its classical counterpart, providing - at most - a quadratic speed-up over the classical solution for unstructured database search. The original formulation of Grover's algorithm is non-deterministic, finding the answer with a probability that varies with the size of the search space and the number of marked elements. A recent reformulation introduced a deterministic form of Grover's algorithm that - in principle - finds the answer with certainty. Here we realise the deterministic Grover's algorithm on a programmable photonic integrated circuit, finding that it not only outperforms the original Grover's algorithm as predicted, but is also markedly more robust against technological imperfections. We explore databases of 4 to 10 elements, with every choice of a single marked element, achieving an average success probability of $99.77 \pm 0.05\%$.
- Abstract（参考訳）: Groverのアルゴリズムは、量子コンピューティングの優位性の先駆的な実証の1つであり、非構造化データベースサーチの古典的解に対する2次的なスピードアップを提供する。
グロバーのアルゴリズムの元々の定式化は非決定論的であり、探索空間のサイズとマークされた要素の数によって異なる確率で解を求める。
最近の改定はグロバーのアルゴリズムの決定論的形式を導入し、原理的にはその解を確実性で見つける。
ここでは、プログラム可能なフォトニック集積回路上でのGroverの決定論的アルゴリズムが、予測したとおりのGroverのアルゴリズムよりも優れているだけでなく、技術的不完全性に対して顕著に堅牢であることを示す。
4から10要素のデータベースを探索し、1つのマークされた要素を選択すれば、平均的な成功確率は99.77 \pm 0.05\%$となる。
関連論文リスト
- Arbitrary state creation via controlled measurement [49.494595696663524]
このアルゴリズムは任意の$n$-qubit純量子重ね合わせ状態を生成し、精度は$m$-decimalsである。
このアルゴリズムは、1キュービット回転、アダマール変換、マルチキュービット制御によるC-NOT演算を使用する。
論文 参考訳（メタデータ） (2025-04-13T07:23:50Z) - On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
格子ベースの暗号は、量子後暗号の主要な候補の1つである。
量子攻撃に対する暗号セキュリティは、最短ベクトル問題(SVP)のような格子問題に基づいている
SVPを解くための漸近的な量子スピードアップはGroverの探索に依存している。
論文 参考訳（メタデータ） (2024-10-17T16:54:41Z) - Near-deterministic quantum search algorithm without phase design [10.754825115553086]
グローバーのアルゴリズムは、4つのうち1つを探索した場合にのみ、確実にターゲット状態を見つけることができる。
決定論的探索アルゴリズムは8,16,32のうち1つを探索する際にも設計される。
論文 参考訳（メタデータ） (2024-07-15T14:20:47Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
近似入力を読み取る際に、LASSOのミニミサの正しいサポートセットを(確率$>1/2$で)決定できないことを示す。
不適切な入力の場合、アルゴリズムは永遠に動作するので、間違った答えを出すことはない。
無限条件数を持つ点を含む開集合上で定義される任意のアルゴリズムに対して、アルゴリズムが永久に実行されるか、間違った解を生成するような入力が存在する。
論文 参考訳（メタデータ） (2023-12-18T18:29:01Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Hybrid classical-quantum text search based on hashing [0.0]
非順序データベースにおける古典的な検索クエリの複雑さは、テキストの長さと与えられた値の長さにおいて線形であることが知られている。
本稿ではGroverの検索を実装した古典量子ハイブリッドアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-11-02T13:16:07Z) - Opening the Black Box Inside Grover's Algorithm [0.0]
グロバーのアルゴリズムは、量子コンピュータが古典的コンピュータよりも有利であることを示す主要なアルゴリズムである。
我々は,古典的コンピュータ上で動作可能な量子インスパイアされたアルゴリズムを構築し,Groverのタスクを,オラクルへの(シミュレーションの)呼び出し数で線形に実行する。
論文 参考訳（メタデータ） (2023-03-20T17:56:20Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Deterministic Grover search with a restricted oracle [2.976027966501599]
グロバーの量子探索アルゴリズムは古典的アルゴリズムよりも二次的な量子的優位性を提供する。
量子探索オラクルをユーザが制御することなく、正しい結果を返すための修正版を提示する。
論文 参考訳（メタデータ） (2022-01-01T02:04:11Z) - Quantum Search with Prior Knowledge [15.384459603233978]
本稿では,Grover の探索アルゴリズムの新たな一般化を提案する。
提案アルゴリズムは,クエリ数が固定された場合の解を見つけるための最適成功確率を実現する。
論文 参考訳（メタデータ） (2020-09-18T09:50:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。