論文の概要: Finding quantum partial assignments by search-to-decision reductions
- arxiv url: http://arxiv.org/abs/2408.03986v1
- Date: Wed, 7 Aug 2024 18:00:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-09 17:39:48.435791
- Title: Finding quantum partial assignments by search-to-decision reductions
- Title（参考訳）: 探索-決定還元による量子部分代入の探索
- Authors: Jordi Weggemans,
- Abstract要約: 量子状態として$mathsfQMA$ oracle の量子アルゴリズムが $mathsfQMA$ を構築可能であることを示す。
量子状態として量子目撃者に興味がないが、その部分的な割り当てだけを考慮すれば、$mathsfQMA$ oracleにアクセスできる古典的な時間アルゴリズムが存在することが証明される。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In computer science, many search problems are reducible to decision problems, which implies that finding a solution is as hard as deciding whether a solution exists. A quantum analogue of search-to-decision reductions would be to ask whether a quantum algorithm with access to a $\mathsf{QMA}$ oracle can construct $\mathsf{QMA}$ witnesses as quantum states. By a result from Irani, Natarajan, Nirkhe, Rao, and Yuen (CCC '22), it is known that this does not hold relative to a quantum oracle, unlike the cases of $\mathsf{NP}$, $\mathsf{MA}$, and $\mathsf{QCMA}$ where search-to-decision relativizes. We prove that if one is not interested in the quantum witness as a quantum state but only in terms of its partial assignments, i.e. the reduced density matrices, then there exists a classical polynomial-time algorithm with access to a $\mathsf{QMA}$ oracle that outputs approximations of the density matrices of a near-optimal quantum witness, for any desired constant locality and inverse polynomial error. Our construction is based on a circuit-to-Hamiltonian mapping that approximately preserves near-optimal $\mathsf{QMA}$ witnesses and a new $\mathsf{QMA}$-complete problem, Low-energy Density Matrix Verification, which is called by the $\mathsf{QMA}$ oracle to adaptively construct approximately consistent density matrices of a low-energy state.
- Abstract（参考訳）: 計算機科学において、多くの探索問題は決定問題に対して再現可能であるため、解を見つけることは解が存在するかどうかを決定するのと同じくらい難しい。
探索対決定還元の量子アナログは、$\mathsf{QMA}$ oracleが量子状態として$\mathsf{QMA}$証人を構成することができるかどうかを問うことである。
イラン語、ナタラジャン語、ニクヘ語、ラオ語、ユエン語(CCC '22)の結果、これは$\mathsf{NP}$, $\mathsf{MA}$, $\mathsf{QCMA}$と異なり、量子オラクルと相対性を持たないことが知られている。
量子ビクターを量子状態として興味がなければ、その部分的な割り当て(すなわち密度行列の減少)によって、任意の所望の局所性および逆多項式誤差に対して、準最適量子ビクターの密度行列の近似を出力する$\mathsf{QMA}$ oracleにアクセスできる古典多項式時間アルゴリズムが存在することを証明している。
我々の構成は、ほぼ最適に近い$\mathsf{QMA}$証人および新しい$\mathsf{QMA}$完全問題である低エネルギー密度行列検証(英語版)に基づいており、これは、低エネルギー状態のほぼ一貫した密度行列を適応的に構築するために$\mathsf{QMA}$オラクルと呼ばれる。
関連論文リスト
- Quantum multi-row iteration algorithm for linear systems with non-square coefficient matrices [7.174256268278207]
古典的マルチロー反復法に着想を得た量子アルゴリズムを提案する。
本アルゴリズムは,不整合系の解法に適した係数行列の要求を小さくする。
論文 参考訳（メタデータ） (2024-09-06T03:32:02Z) - 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 sampling algorithms for quantum state preparation and matrix block-encoding [0.0]
まず、量子状態 $|psi_frangle propto sumN_x=1 f(x)|xrangle$ を作成するQRSに基づくアルゴリズムを提案する。
次に、QRSの手法を行列ブロック符号化問題に適用し、与えられた行列をブロック符号化するためのQRSベースのアルゴリズムを、与えられた行列の和 A = sum_ij A_ij |irangle langle j|$ で導入する。
論文 参考訳（メタデータ） (2024-05-19T03:46:11Z) - Quantum State Learning Implies Circuit Lower Bounds [2.2667044928324747]
状態トモグラフィー、擬似ランダム性、量子状態、回路下界の接続を確立する。
わずかに自明な量子状態トモグラフィーアルゴリズムでさえも量子状態合成に関する新しい言明に繋がることを示した。
論文 参考訳（メタデータ） (2024-05-16T16:46:27Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳（メタデータ） (2024-01-17T18:59:38Z) - On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms [0.0]
NPにおける制約満足度問題の特徴は近似硬度であり、最悪の場合、十分な品質の近似解を見つけることは指数関数的に困難である。
ハミルトニアン時間進化に基づくアルゴリズムでは、原型的にハードなMAX-3-XORSAT問題クラスを通してこの問題を探索する。
近似系におけるランダムなハイパーグラフに対して、エネルギーを$E = N_mathrmunsat-N_mathrmsat$と定義すれば、スペクトルフィルタリングされた量子最適化は$E leq q_mで状態を返す。
論文 参考訳（メタデータ） (2023-12-11T04:15:55Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Quantum search-to-decision reductions and the state synthesis problem [0.4248594146171025]
量子アルゴリズムは古典的な決定オラクルにクエリを行い、所望の量子状態を出力することを示す。
また、逆精度まで$mathsfQMA$問題の証人を生成する量子時間アルゴリズムが存在することも示している。
また、より一般的な$textitstate合成問題$を探索し、ターゲット状態の効率的な合成を目標とする。
論文 参考訳（メタデータ） (2021-11-04T16:52:58Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
3次元形状と画像のマッチング問題は、NPハードな置換行列制約を持つ二次代入問題(QAP)としてしばしば定式化される。
本稿では,量子ハードウェア上での効率的な実行に適した制約のない問題として,いくつかのQAPの再構成を提案する。
提案アルゴリズムは、将来の量子コンピューティングアーキテクチャにおいて、より高次元にスケールする可能性がある。
論文 参考訳（メタデータ） (2021-07-08T17:59:55Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。