論文の概要: Pseudo-deterministic Quantum Algorithms

• arxiv url: http://arxiv.org/abs/2602.17647v1
• Date: Thu, 19 Feb 2026 18:54:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-20 15:21:29.409371
• Title: Pseudo-deterministic Quantum Algorithms
• Title（参考訳）: 擬似決定論的量子アルゴリズム
• Authors: Hugo Aaronson, Tom Gur, Jiawei Li,
• Abstract要約: 任意の総和$R$に対して、擬似決定論的量子アルゴリズムは、決定論的アルゴリズムよりも極端に有利であることを示す。 アルゴリズムの面では、少ないオーバーヘッドで擬似決定論的にできる量子探索問題のクラスを同定する。
• 参考スコア（独自算出の注目度）: 7.46931129146594
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We initiate a systematic study of pseudo-deterministic quantum algorithms. These are quantum algorithms that, for any input, output a canonical solution with high probability. Focusing on the query complexity model, our main contributions include the following complexity separations, which require new lower bound techniques specifically tailored to pseudo-determinism: - We exhibit a problem, Avoid One Encrypted String (AOES), whose classical randomized query complexity is $O(1)$ but is maximally hard for pseudo-deterministic quantum algorithms ($Ω(N)$ query complexity). - We exhibit a problem, Quantum-Locked Estimation (QL-Estimation), for which pseudo-deterministic quantum algorithms admit an exponential speed-up over classical pseudo-deterministic algorithms ($O(\log(N))$ vs. $Θ(\sqrt{N})$), while the randomized query complexity is $O(1)$. Complementing these separations, we show that for any total problem $R$, pseudo-deterministic quantum algorithms admit at most a quintic advantage over deterministic algorithms, i.e., $D(R) = \tilde O(psQ(R)^5)$. On the algorithmic side, we identify a class of quantum search problems that can be made pseudo-deterministic with small overhead, including Grover search, element distinctness, triangle finding, $k$-sum, and graph collision.
• Abstract（参考訳）: 擬似決定論的量子アルゴリズムの体系的研究を開始する。 これらは、任意の入力に対して高い確率で正準解を出力する量子アルゴリズムである。 従来のランダム化クエリの複雑さは$O(1)$だが、疑似決定論的量子アルゴリズム(Ω(N)$クエリの複雑性)では極端に難しい。 疑似決定論的量子アルゴリズムは、古典的擬似決定論的アルゴリズム(O(\log(N))$ vs. $s(\sqrt{N})$)よりも指数的なスピードアップを許容するが、ランダム化されたクエリ複雑性は$O(1)$である。 これらの分離を補完すると、任意の全問題$R$に対して、擬決定論的量子アルゴリズムは決定論的アルゴリズムよりも極端に有利である、すなわち$D(R) = \tilde O(psQ(R)^5)$であることを示す。 アルゴリズム面では、Grover検索、要素差分性、三角形探索、$k$-sum、グラフ衝突など、小さなオーバーヘッドで擬似決定論的にできる量子探索問題のクラスを同定する。

関連論文リスト

• Limitation of Quantum Walk Approach to the Maximum Matching Problem [0.0]
  最大マッチング問題は、隣接行列で表される$n$頂点上のグラフに対して$Omega(n3/2)$以下の量子クエリ複雑性を持つ。 現在の最良の量子アルゴリズムは、クエリ複雑性$O(n7/4)$であり、これは自明な有界な$O(n2)$に対する改善である。 量子ウォーク法は、既知の(あるいは自明な)上界をクエリの複雑さで改善する高速なアルゴリズムを作成できないことを示す。
  論文  参考訳（メタデータ） (2025-10-30T08:29:44Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。 この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。 我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
  論文  参考訳（メタデータ） (2024-05-02T10:29:06Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem [0.0]
  この研究は、よく知られた溶接木問題に対する量子アルゴリズムを再考する。 最も単純な量子ウォークに基づく非常に簡潔な量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-17T16:03:50Z)
• On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
  我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。 我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
  論文  参考訳（メタデータ） (2023-03-20T08:17:32Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Variational learning algorithms for quantum query complexity [3.980076328494117]
  量子クエリの複雑さを研究するための変分学習アルゴリズムを開発した。 量子クエリの複雑さの様々なケースを解析するために,本手法を適用した。 本手法は,NISQ(Noisy Intermediate-Scale Quantum)デバイス上で容易に実装できる。
  論文  参考訳（メタデータ） (2022-05-16T05:16:15Z)
• Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
  入力および出力システムへのブラックボックスアクセスを前提として,最初の効率的な量子因果順序探索アルゴリズムを開発した。 我々は、量子コムを用いて因果順序をモデル化し、我々のアルゴリズムは、与えられたプロセスと互換性のある入力と出力の順序を出力する。 我々のアルゴリズムは、量子通信ネットワークで利用可能な伝送経路を効率的に検出し、最適化する方法を提供する。
  論文  参考訳（メタデータ） (2020-12-03T07:12:08Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。