論文の概要: On the complexity of unique quantum witnesses and quantum approximate counting

• arxiv url: http://arxiv.org/abs/2410.23811v2
• Date: Thu, 18 Sep 2025 04:58:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-19 17:26:52.835598
• Title: On the complexity of unique quantum witnesses and quantum approximate counting
• Title（参考訳）: ユニークな量子目撃者の複雑性と量子近似計数について
• Authors: Anurag Anshu, Jonas Haferkamp, Yeongwoo Hwang, Quynh T. Nguyen,
• Abstract要約: 量子オラクルを$mathsfBQPmathsfUniqueQMA$と$mathsfQMA$で分離する。 局所ハミルトン問題のどんな構造的特性を活用できるのか? 局所ハミルトンの基底エネルギーを$mathsfUniqueQMA$プロトコルで推定できることを示すことによって、物理的動機付けの候補を導入する。
• 参考スコア（独自算出の注目度）: 2.4475760284813255
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the long-standing open question on the power of unique witnesses in quantum protocols, which asks if $\textsf{UniqueQMA}$, a variant of $\textsf{QMA}$ whose accepting witness space is 1-dimensional, contains $\mathsf{QMA}$ under quantum reductions. This work rules out any black-box reduction from $\mathsf{QMA}$ to $\mathsf{UniqueQMA}$ by showing a quantum oracle separation between $\mathsf{BQP}^\mathsf{UniqueQMA}$ and $\mathsf{QMA}$. This provides a contrast to the classical case, where the Valiant-Vazirani theorem shows a black-box randomized reduction from $\mathsf{UniqueNP}$ to $\mathsf{NP}$, and suggests the need for studying the structure of the ground space of local Hamiltonians in distilling a potential unique witness. Via similar techniques, we show, relative to a quantum oracle, that $\mathsf{QMA}^\mathsf{QMA}$ cannot decide quantum approximate counting, ruling out a quantum analogue of Stockmeyer's algorithm in the black-box setting. We then ask a natural question; what structural properties of the local Hamiltonian problem can we exploit? We introduce a physically motivated candidate by showing that the ground energy of local Hamiltonians that satisfy a computational variant of the eigenstate thermalization hypothesis (ETH) can be estimated through a $\mathsf{UniqueQMA}$ protocol. Our protocol can be viewed as a quantum expander test in a low energy subspace of the Hamiltonian and verifies a unique entangled state across two copies of the subspace. This allows us to conclude that if $\mathsf{UniqueQMA}$ is not equivalent to $\mathsf{QMA}$, then $\mathsf{QMA}$-hard Hamiltonians must violate ETH under adversarial perturbations. This also serves as evidence that chaotic local Hamiltonians, such as the SYK model may be computationally simpler than general local Hamiltonians.
• Abstract（参考訳）: 我々は、量子プロトコルにおける一意の目撃者の力に関する長年にわたるオープンな質問について研究し、量子還元の下で、受理された証人空間が 1 次元である $\textsf{QMA}$ の変種である $\textsf{UniqueQMA}$ が $\mathsf{QMA}$ を含むかどうかを問う。 この研究は、$\mathsf{QMA}$から$\mathsf{UniqueQMA}$へのブラックボックス還元を、$\mathsf{BQP}^\mathsf{UniqueQMA}$と$\mathsf{QMA}$の間の量子オラクル分離を示すことによって規定する。 これは古典的なケースとは対照的であり、ヴァリアント・ヴァジラニの定理は、ブラックボックスのランダム化を$\mathsf{UniqueNP}$から$\mathsf{NP}$に還元することを示している。 類似した手法により、量子オラクルと比較して、$\mathsf{QMA}^\mathsf{QMA}$は量子近似カウントを決定できず、ブラックボックス設定でストックメイヤーのアルゴリズムの量子アナログを除外することを示した。 局所ハミルトン問題のどんな構造的特性を活用できるのか? 固有状態熱化仮説(ETH)の計算変量を満たす局所ハミルトニアンの基底エネルギーは、$\mathsf{UniqueQMA}$プロトコルによって推定できることを示すことによって、物理的動機付けの候補を導入する。 我々のプロトコルは、ハミルトニアンの低エネルギー部分空間における量子展開テストと見なすことができ、部分空間の2つのコピーにまたがる一意の絡み合った状態を検証することができる。 これにより、$\mathsf{UniqueQMA}$ が $\mathsf{QMA}$ に同値でないなら、$\mathsf{QMA}$-hard Hamiltonian は敵の摂動の下で ETH を破らなければならないと結論付けることができる。 これはまた、SYKモデルのようなカオス的局所ハミルトニアンが一般の局所ハミルトニアンよりも計算的に単純であることを示す証拠でもある。

関連論文リスト

• Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions [1.43494686131174]
  1-varepsilon)n)$ for any $varepsilon>0$ for any $varepsilon>0$ under the Strong Exponential-Time hypothesis (SETH)。 我々は、任意の1/mathrmpoly(n)$相対誤差に対して$O(sqrt2n)$ timeで実行し、下位境界にマッチし、Bravyi、Chowdhury、Gossによる最先端アルゴリズムを改善する量子アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2026-02-16T01:11:55Z)
• Twin Hamiltonians, three types of the Dyson maps, and the probabilistic interpretation problem in quasi-Hermitian quantum mechanics [3.7723788828505125]
  準エルミート量子力学において、ハミルトニアンの最適で計算に優しい形式は一般に非エルミート的、$H neq Hdagger$である。 ここでは、Dyson map $: H to Mathfrakh$を介して$H$をHermitian形式に変換するという代替戦略に焦点をあてる。 このエルミートアイソスペクトル双対$mathfrakh$の$H$の構成は、従来の量子物理学と古典物理学の対応原理を復元するだけでなく、その網羅的な枠組みも提供する。
  論文  参考訳（メタデータ） (2025-11-25T15:33:31Z)
• Hamiltonian Decoded Quantum Interferometry [69.7049555871155]
  我々は、ハミルトニアン復号量子干渉計(HDQI)を紹介する。 HDQIはコヒーレントな測定とパウリ群のシンプレクティック表現を利用して、ギブスサンプリングとハミルトン・ベリアンを減少させる。 そこで,HDQI はギブズ状態を任意の温度で効率的に生成し,物理的にモチベーションを持つハミルトニアンのクラスに適応することを示した。
  論文  参考訳（メタデータ） (2025-10-09T08:06:15Z)
• Quantum chemistry with provable convergence via randomized sample-based quantum diagonalization [0.0]
  我々は、SKQDとハミルトンプロパゲータのqDRIFTランダム化コンパイルを組み合わせた新しいSQD変種を導入する。 結果のアルゴリズムであるSqDRIFTは、化学ハミルトニアンの実用スケールでのSQD計算を可能にする。
  論文  参考訳（メタデータ） (2025-08-04T16:36:12Z)
• Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy [0.7321157455672144]
  証明に特有の量子古典的PCPの制限は、そのパワーを低下させるものではないことを示す。 また、カルプ・リプトンの定理の非一様量子類似性も証明する。 これらの結果は、量子証明システムの構造に関する新たな洞察を与える。
  論文  参考訳（メタデータ） (2025-06-24T16:59:50Z)
• Super Quantum Mechanics [37.69303106863453]
  超量子力学(SQM)は、ヒルベルト空間における状態が複数の二次的制約を受けることを考慮した理論である。 この場合、定常SQM問題は、機械学習と人工知能に複数の応用がある量子逆問題である。
  論文  参考訳（メタデータ） (2025-01-25T19:41:04Z)
• Hilbert space geometry and quantum chaos [39.58317527488534]
  種々の多パラメータランダム行列ハミルトン多様体に対するQGTの対称部分を考える。 エルゴード位相は滑らかな多様体に対応するが、可積分極限は円錐欠陥を持つ特異幾何として自身を示す2次元パラメータ空間を求める。
  論文  参考訳（メタデータ） (2024-11-18T19:00:17Z)
• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。 この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。 ポアソン・ファインマン・カック法を用いて古典的な緩やかな混合結果を持ち上げる方法を示す。
  論文  参考訳（メタデータ） (2024-11-06T22:51:27Z)
• Quantum State Transfer in Interacting, Multiple-Excitation Systems [41.94295877935867]
  量子状態伝達(QST)は、あるノードから別のノードへの量子情報のコヒーレントな通過を記述する。 高忠実度QSTを与えるハミルトニアンの発見を可能にするモンテカルロ法について述べる。 その結果生まれたJaynes-Cummings-Hubbardと周期的なAndersonモデルは、原則として、効率的なQSTを提供するための適切なハードウェアで設計することができる。
  論文  参考訳（メタデータ） (2024-05-10T23:46:35Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds [1.3927943269211591]
  本研究は、$mathsfPH$の量子検証に基づく3つの一般化を研究する。 まず、[GSSSY22] から、崩壊定理と$mathsfQCPH$に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。 我々は、$mathsfpureQPH$に対する一方の誤り低減と、これらの量子変量$mathsfPH$に関する最初の境界を示す。
  論文  参考訳（メタデータ） (2024-01-03T09:12:25Z)
• Quantum State Tomography for Matrix Product Density Operators [28.799576051288888]
  実験的測定から量子状態の再構成は、量子デバイスの検証とベンチマークに不可欠である。 ノイズや中間スケールの量子コンピュータによって生成される状態のような多くの物理量子状態は通常、構造化される。 圧縮センシングのツールと経験過程の理論を用いて,MPOの安定回復の理論的保証を確立する。
  論文  参考訳（メタデータ） (2023-06-15T18:23:55Z)
• Quantum state testing beyond the polarizing regime and quantum triangular discrimination [0.2538209532048867]
  三角微分やジェンセン・シャノンの発散に関する時間境界分布試験問題に対して適切な量子アナログを導入する。 我々の研究は、これらの問題に対する適切な量子アナログを導入し、三角形の識別のための量子の類似を定義する。 これらの新しい$mathsfQSZK$-complete問題により、$mathsfQSZK$は偏光系を超えた$mathrmQSDP$を含む。
  論文  参考訳（メタデータ） (2023-03-03T14:25:18Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  量子コンピュータの候補は、量子システムの低温特性をシミュレートすることである。 本稿は、ほとんどのランダムハミルトニアンに対して、最大混合状態は十分に良い試行状態であることを示す。 位相推定は、基底エネルギーに近いエネルギーの状態を効率的に生成する。
  論文  参考訳（メタデータ） (2023-02-07T10:57:36Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Quantum annealing with symmetric subspaces [0.0]
  我々は、より効率的な量子アニーリング(QA)のために、ハミルトニアン問題の対称性を保存する駆動ハミルトニアンを提案する。 非断熱遷移は特定の部分空間内でのみ起こるので、我々のアプローチは望ましくない非断熱遷移を抑制する可能性がある。 提案手法は, 目標基底状態とQA後の状態との忠実度の観点から, 従来のスキームよりも優れていた。
  論文  参考訳（メタデータ） (2022-09-20T09:44:23Z)
• Theory of Quantum Generative Learning Models with Maximum Mean Discrepancy [67.02951777522547]
  量子回路ボルンマシン(QCBM)と量子生成逆ネットワーク(QGAN)の学習可能性について検討する。 まず、QCBMの一般化能力を解析し、量子デバイスがターゲット分布に直接アクセスできる際の優位性を同定する。 次に、QGANの一般化誤差境界が、採用されるAnsatz、クォーディットの数、入力状態に依存することを示す。
  論文  参考訳（メタデータ） (2022-05-10T08:05:59Z)
• Quantum Davidson Algorithm for Excited States [42.666709382892265]
  基底状態と励起状態の両方に対処するために量子クリロフ部分空間(QKS)法を導入する。 固有状態の残余を使ってクリロフ部分空間を拡大し、コンパクトな部分空間を定式化し、正確な解と密接に一致させる。 量子シミュレータを用いて、様々なシステムの励起状態特性を探索するために、新しいQDavidsonアルゴリズムを用いる。
  論文  参考訳（メタデータ） (2022-04-22T15:03:03Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
  量子系 $S$ に関連する可観測物は非可換代数 $mathcal A_S$ を形成する。 密度行列 $rho$ は可観測物の期待値から決定できると仮定される。 アーベル代数は内部自己同型を持たないので、測定装置は可観測物の平均値を決定することができる。
  論文  参考訳（メタデータ） (2021-12-14T16:29:53Z)
• Quantum double aspects of surface code models [77.34726150561087]
  基礎となる量子double $D(G)$対称性を持つ正方格子上でのフォールトトレラント量子コンピューティングの北エフモデルを再検討する。 有限次元ホップ代数$H$に基づいて、我々の構成がどのように$D(H)$モデルに一般化するかを示す。
  論文  参考訳（メタデータ） (2021-06-25T17:03:38Z)
• Dynamical Self-energy Mapping (DSEM) for quantum computing [0.0]
  ノイズの多い中間スケール量子(NISQ)デバイスでは、コヒーレンスに制限のある適度な数の量子ビットしか利用できない。 古典量子ハイブリッドアルゴリズムを用いて,NISQデバイス上での分子化学シミュレーションにおいて,この課題を回避する方法を提案する。
  論文  参考訳（メタデータ） (2020-10-12T04:12:21Z)
• Quantum-optimal-control-inspired ansatz for variational quantum algorithms [105.54048699217668]
  変分量子アルゴリズム (VQA) の中心成分は状態準備回路(英語版)であり、アンザッツ(英語版)または変分形式(英語版)とも呼ばれる。 ここでは、対称性を破るユニタリを組み込んだ「解」を導入することで、このアプローチが必ずしも有利であるとは限らないことを示す。 この研究は、より一般的な対称性を破るアンスの開発に向けた第一歩となり、物理学や化学問題への応用に繋がる。
  論文  参考訳（メタデータ） (2020-08-03T18:00:05Z)
• Testing a quantum annealer as a quantum thermal sampler [0.3437656066916039]
  D-Wave 2000Q量子アニールプロセッサを用いた正準一次元横場イジングモデルの対角熱特性について検討した。 量子プロセッサは、Quantum Monte Carloによって予測される正しい期待値の生成に失敗する。 任意の量子多体系に対して、熱予測値が一般に頑健に見積もることができるのかは、未解決の問題である。
  論文  参考訳（メタデータ） (2020-02-29T23:06:39Z)
• Relating relative R\'enyi entropies and Wigner-Yanase-Dyson skew information to generalized multiple quantum coherences [0.0]
  本稿では、$alpha$-MQCsという、$alpha$-relative purityに基づく多重量子コヒーレンスの新しいクラスについて検討する。 我々のフレームワークは、$alpha$-MQCsをWigner-Yanase-Dysonスキュー情報にリンクできる。 これらのアイデアは、単一量子状態、二量子ベル対角状態、多粒子混合状態の幅広いクラスによって記述される量子系に対するものである。
  論文  参考訳（メタデータ） (2020-02-25T21:12:32Z)

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

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