論文の概要: stateQIP = statePSPACE
- arxiv url: http://arxiv.org/abs/2301.07730v2
- Date: Mon, 10 Apr 2023 17:12:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-11 21:05:26.969906
- Title: stateQIP = statePSPACE
- Title（参考訳）: stateQIP = statePSPACE
- Authors: Tony Metger, Henry Yuen
- Abstract要約: 本研究では,SDPPSPACEと状態QIPの2つの状態クラスの関係について検討する。
私たちの主な結果は、リバースインクルージョン、stateQIP $subseteq$ statePSPACEです。
また、一般的な量子対話プロトコルの最適証明戦略を量子空間で実装できることも示している。
- 参考スコア（独自算出の注目度）: 0.15229257192293197
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Complexity theory traditionally studies the hardness of solving classical
computational problems. In the quantum setting, it is also natural to consider
a different notion of complexity, namely the complexity of physically preparing
a certain quantum state. We study the relation between two such state
complexity classes: statePSPACE, which contains states that can be generated by
space-uniform polynomial-space quantum circuits, and stateQIP, which contains
states that a polynomial-time quantum verifier can generate by interacting with
an all-powerful untrusted quantum prover. The latter class was recently
introduced by Rosenthal and Yuen (ITCS 2022), who proved that statePSPACE
$\subseteq$ stateQIP.
Our main result is the reverse inclusion, stateQIP $\subseteq$ statePSPACE,
thereby establishing equality of the two classes and providing a natural
state-complexity analogue to the celebrated QIP = PSPACE theorem of Jain, et
al. (J. ACM 2011). To prove this, we develop a polynomial-space quantum
algorithm for solving a large class of exponentially large "PSPACE-computable"
semidefinite programs (SDPs), which also prepares an optimiser encoded in a
quantum state. Our SDP solver relies on recent block-encoding techniques from
quantum algorithms, demonstrating that these techniques are also useful for
complexity theory.
Using similar techniques, we also show that optimal prover strategies for
general quantum interactive protocols can be implemented in quantum polynomial
space. We prove this by studying an algorithmic version of Uhlmann's theorem
and establishing an upper bound on the complexity of implementing Uhlmann
transformations.
- Abstract（参考訳）: 複雑性理論は伝統的に古典的な計算問題を解くことの難しさを研究する。
量子設定において、異なる複雑性の概念、すなわちある量子状態を物理的に準備する複雑さを考えることも自然である。
空間一様多項式空間量子回路で生成可能な状態を含む状態PSPACEと、全能不信頼な量子証明器と相互作用することによって多項式時間量子検証器が生成できる状態を含む状態QIPの関係について検討する。
後者のクラスは、最近Rosenhal and Yuen (ITCS 2022) によって導入され、 statePSPACE $\subseteq$ stateQIP が証明された。
我々の主な結果は、逆包含状態 QIP $\subseteq$ statePSPACE であり、2つのクラスの等式を確立し、ジャイナ等の有名なQIP = PSPACE定理に類似した自然な状態複素性を与える(J. ACM 2011)。
これを証明するために、指数関数的に大きいPSPACE計算可能な半定値プログラム(SDP)を解く多項式空間量子アルゴリズムを開発し、量子状態に符号化されたオプティマイザを準備する。
我々のSDPソルバは量子アルゴリズムの最近のブロック符号化技術に依存しており、これらの手法が複雑性理論にも有用であることを示す。
同様の手法を用いて、一般的な量子対話プロトコルの最適証明戦略を量子多項式空間に実装できることを示した。
我々は、uhlmannの定理のアルゴリズム版を研究し、uhlmann変換を実装する複雑さの上限を確立することによってこれを証明する。
関連論文リスト
- Complexity Theory for Quantum Promise Problems [5.049812996253858]
本稿では,量子暗号と複雑性理論の関係,特にImpagliazzoの5つの世界の枠組みについて考察する。
複雑性クラス p/mBQP, p/mQ(C)MA, $mathrmp/mQSZK_hv$, p/mQIP, p/mPSPACE に注目する。
我々は、このフレームワークを暗号に適用し、一方通行状態生成器、擬似ランダム状態、EFIがmQCMAで束縛されていることを示す。
論文 参考訳（メタデータ） (2024-11-06T07:29:52Z) - Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳（メタデータ） (2024-08-22T08:21:28Z) - Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem [70.42372213666553]
No-Free-Lunch(NFL)定理は、最適化プロセスに関係なく問題とデータ非依存の一般化誤差を定量化する。
我々は、様々な量子学習アルゴリズムを、特定の観測可能条件下で量子力学を学習するために設計された3つの学習プロトコルに分類する。
得られたNFL定理は, CLC-LP, ReQu-LP, Qu-LPにまたがるサンプルの複雑性を2次的に低減することを示した。
この性能差は、非直交量子状態のグローバル位相に関する情報を間接的に活用するために、量子関連学習プロトコルのユニークな能力に起因している。
論文 参考訳（メタデータ） (2024-05-12T09:05:13Z) - Towards Quantum Computational Mechanics [1.530480694206666]
本稿では、量子コンピューティングを用いて、計算ホモジェナイゼーションにおける代表要素体積(RVE)問題を解く方法について述べる。
我々の量子RVE解法は古典解法に対して指数加速度を得る。
論文 参考訳（メタデータ） (2023-12-06T12:53:02Z) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
期待されている量子コンピュータの応用は、科学と産業にまたがる。
本稿では,量子アルゴリズムの応用分野について検討する。
私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
論文 参考訳（メタデータ） (2023-10-04T17:53:55Z) - Quantum Signal Processing with the one-dimensional quantum Ising model [0.0]
量子信号処理(QSP)は、量子システムの特性を操作および決定するための有望なフレームワークとして登場した。
我々は、時空双対量子回路や量子シミュレーションから量子制御まで、様々な分野における我々のアプローチの例と応用について述べる。
論文 参考訳（メタデータ） (2023-09-08T18:01:37Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
単一画像超解像(SISR)問題を解くために,量子コンピューティングに基づくアルゴリズムを提案する。
提案したAQCアルゴリズムは、SISRの精度を維持しつつ、古典的なアナログよりも向上したスピードアップを実現する。
論文 参考訳（メタデータ） (2023-04-18T11:57:15Z) - Quantum Merlin-Arthur proof systems for synthesizing quantum states [0.0]
クラスNP合成における状態合成法について検討した。
我々は、最も自然な候補者の1つであるUQMA目撃者の家族が国家QMAであることを確認した。
状態QCMAが完全性を達成することを実証する。
論文 参考訳（メタデータ） (2023-03-03T12:14:07Z) - Quantum process tomography of continuous-variable gates using coherent
states [49.299443295581064]
ボソニックモード超伝導回路におけるコヒーレント状態量子プロセストモグラフィ(csQPT)の使用を実証する。
符号化量子ビット上の変位とSNAP演算を用いて構築した論理量子ゲートを特徴付けることにより,本手法の結果を示す。
論文 参考訳（メタデータ） (2023-03-02T18:08:08Z) - Interactive Proofs for Synthesizing Quantum States and Unitaries [0.15229257192293197]
量子状態の構築やユニタリ変換の実行など、本質的に量子演算の複雑さについて検討する。
量子状態とユニタリの対話的証明のモデルを定義する。
複数の絡み合ったプロバーの設定でも類似した結果が得られる。
論文 参考訳（メタデータ） (2021-08-16T15:59:33Z) - On exploring the potential of quantum auto-encoder for learning quantum systems [60.909817434753315]
そこで我々は,古典的な3つのハードラーニング問題に対処するために,QAEに基づく効果的な3つの学習プロトコルを考案した。
私たちの研究は、ハード量子物理学と量子情報処理タスクを達成するための高度な量子学習アルゴリズムの開発に新たな光を当てています。
論文 参考訳（メタデータ） (2021-06-29T14:01:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。