論文の概要: BQP, meet NP: Search-to-decision reductions and approximate counting
- arxiv url: http://arxiv.org/abs/2401.03943v1
- Date: Mon, 8 Jan 2024 14:59:48 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-09 15:27:57.649946
- Title: BQP, meet NP: Search-to-decision reductions and approximate counting
- Title（参考訳）: BQP, meet NP: Search-to-Decision reductions and almost counting
- Authors: Sevag Gharibian and Jonas Kamminga
- Abstract要約: 本稿では,探索-決定還元と近似カウントという,ブール充足可能性(SAT)問題の研究の2つの基本的な課題に焦点をあてる。
まず、ポリ時間チューリングマシンがNPオラクルに対して$Theta(n)$クエリを必要とする古典的な設定とは対照的に、量子的には$Theta(log n)$クエリが十分であることを示す。
近似カウンティングに移行し、探索-決定還元と近似カウンティングの量子リンクを利用して、既存の古典的近似カウンティングアルゴリズムが最適であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: What is the power of polynomial-time quantum computation with access to an NP
oracle? In this work, we focus on two fundamental tasks from the study of
Boolean satisfiability (SAT) problems: search-to-decision reductions, and
approximate counting. We first show that, in strong contrast to the classical
setting where a poly-time Turing machine requires $\Theta(n)$ queries to an NP
oracle to compute a witness to a given SAT formula, quantumly $\Theta(\log n)$
queries suffice. We then show this is tight in the black-box model - any
quantum algorithm with "NP-like" query access to a formula requires
$\Omega(\log n)$ queries to extract a solution with constant probability.
Moving to approximate counting of SAT solutions, by exploiting a quantum link
between search-to-decision reductions and approximate counting, we show that
existing classical approximate counting algorithms are likely optimal. First,
we give a lower bound in the "NP-like" black-box query setting: Approximate
counting requires $\Omega(\log n)$ queries, even on a quantum computer. We then
give a "white-box" lower bound (i.e. where the input formula is not hidden in
the oracle) - if there exists a randomized poly-time classical or quantum
algorithm for approximate counting making $o(log n)$ NP queries, then
$\text{BPP}^{\text{NP}[o(n)]}$ contains a $\text{P}^{\text{NP}}$-complete
problem if the algorithm is classical and $\text{FBQP}^{\text{NP}[o(n)]}$
contains an $\text{FP}^{\text{NP}}$-complete problem if the algorithm is
quantum.
- Abstract（参考訳）: np oracleにアクセスした多項式時間量子計算のパワーは何でしょうか。
本研究では,探索と判定の削減と近似カウントという,ブール充足可能性(SAT)問題の研究の2つの基本的な課題に焦点をあてる。
まず、ポリ時間チューリングマシンが与えられたSAT公式の証人を計算するためにNPオラクルに$\Theta(n)$クエリを必要とする古典的な設定とは対照的に、量子的に$\Theta(\log n)$クエリが十分であることを示す。
式への"NPライクな"クエリアクセスを持つ任意の量子アルゴリズムは、一定の確率で解を抽出するために$\Omega(\log n)$クエリを必要とする。
SAT解の近似カウントに移行し、探索-決定還元と近似カウントの量子リンクを利用して、既存の古典的近似カウントアルゴリズムが最適であることを示す。
まず、"npライクな"ブラックボックスクエリの設定において下限を与える:近似カウントは量子コンピュータ上でさえ$\omega(\log n)$クエリを必要とする。
すると、「ホワイトボックス」の下界(すなわち、入力公式がオラクルに隠されていない場合)を与える -$o(log n)$ NPクエリを作るためにランダム化されたポリ時間古典的あるいは量子的アルゴリズムが存在するなら、$\text{BPP}^{\text{NP}[o(n)]}$は古典的であれば$\text{P}^{\text{NP}}$-完全問題を含み、$\text{FQP}^{\text{NP}[o(n)]}$は量子的であれば$\text{FP}^{\text{NP}}$-完全問題を含む。
関連論文リスト
- 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) - Efficient Quantum State Synthesis with One Query [0.0]
本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。
我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
論文 参考訳（メタデータ） (2023-06-02T17:49:35Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - 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) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Quantum search-to-decision reductions and the state synthesis problem [0.4248594146171025]
量子アルゴリズムは古典的な決定オラクルにクエリを行い、所望の量子状態を出力することを示す。
また、逆精度まで$mathsfQMA$問題の証人を生成する量子時間アルゴリズムが存在することも示している。
また、より一般的な$textitstate合成問題$を探索し、ターゲット状態の効率的な合成を目標とする。
論文 参考訳（メタデータ） (2021-11-04T16:52:58Z) - A quantum algorithm for computing the Carmichael function [0.0]
量子コンピュータは、多くの数理論問題を効率的に解くことができる。
本稿では,任意の整数$N$に対して,所望の 1 に近い確率でカーマイケル関数を計算するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-11-03T19:30:27Z) - Time and Query Optimal Quantum Algorithms Based on Decision Trees [2.492300648514128]
量子アルゴリズムは時間$tilde O(sqrtGT)$で実装可能であることを示す。
本アルゴリズムは,非バイナリスパンプログラムとその効率的な実装に基づいている。
論文 参考訳（メタデータ） (2021-05-18T06:51:11Z) - Fast Classical and Quantum Algorithms for Online $k$-server Problem on
Trees [0.19573380763700712]
木上の$k$サーバ問題に対するオンラインアルゴリズムを検討する。
Chrobak と Larmore は最適な競合比を持つこの問題に対して$k$-competitive アルゴリズムを提案した。
本稿では,前処理に要するO(nlog n)$時間複雑性を持つ新しい時間効率アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-08-01T14:21:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。