論文の概要: 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モデルのようなカオス的局所ハミルトニアンが一般の局所ハミルトニアンよりも計算的に単純であることを示す証拠でもある。

関連論文リスト

• Quantum chemistry with provable convergence via randomized sample-based quantum diagonalization [0.0]
  我々は、SKQDとハミルトンプロパゲータのqDRIFTランダム化コンパイルを組み合わせた新しいSQD変種を導入する。 結果のアルゴリズムであるSqDRIFTは、化学ハミルトニアンの実用スケールでのSQD計算を可能にする。
  論文  参考訳（メタデータ） (2025-08-04T16:36:12Z)
• 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)
• 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 State Tomography for Matrix Product Density Operators [28.799576051288888]
  実験的測定から量子状態の再構成は、量子デバイスの検証とベンチマークに不可欠である。 ノイズや中間スケールの量子コンピュータによって生成される状態のような多くの物理量子状態は通常、構造化される。 圧縮センシングのツールと経験過程の理論を用いて,MPOの安定回復の理論的保証を確立する。
  論文  参考訳（メタデータ） (2023-06-15T18:23:55Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  量子コンピュータの候補は、量子システムの低温特性をシミュレートすることである。 本稿は、ほとんどのランダムハミルトニアンに対して、最大混合状態は十分に良い試行状態であることを示す。 位相推定は、基底エネルギーに近いエネルギーの状態を効率的に生成する。
  論文  参考訳（メタデータ） (2023-02-07T10:57:36Z)
• 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)
• 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)

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

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