論文の概要: stateQIP = statePSPACE
- arxiv url: http://arxiv.org/abs/2301.07730v1
- Date: Wed, 18 Jan 2023 19:00:17 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-20 16:21:07.458897
- Title: stateQIP = statePSPACE
- Title(参考訳): stateQIP = statePSPACE
- Authors: Tony Metger, Henry Yuen
- Abstract要約: 空間一様の複雑性空間量子回路で生成可能な状態を含む状態PSPACEと、全能量子証明器と相互作用してa時間量子検証器が生成できる状態を含む状態QIPの2つの状態クラスについて検討する。
我々のSDPは近年の量子アルゴリズムによるブロック符号化技術に依存しており、これらの手法が複雑性理論にも有用であることを示す。
- 参考スコア(独自算出の注目度): 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 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変換を実装する複雑さの上限を確立することによってこれを証明する。
関連論文リスト
- Towards Quantum Computational Mechanics [1.7201069233638664]
本稿では、量子コンピューティングを用いて、計算ホモジェナイゼーションにおける代表体積要素(RVE)問題を解く方法について述べる。
我々の量子RVE解法は古典解法に対して指数加速度を得る。
論文 参考訳(メタデータ) (2023-12-06T12:53:02Z) - Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - 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) - Unitary Complexity and the Uhlmann Transformation Problem [41.67228730328207]
本稿では, 単項合成問題の枠組みを導入し, 還元と単項複雑性クラスについて考察する。
このフレームワークは、ある絡み合った状態が局所的な操作によって別の状態に変換される複雑さを研究するのに使用します。
そこで我々は,多くの自然量子情報処理タスクの計算複雑性を研究するための新しい手法を提案する。
論文 参考訳(メタデータ) (2023-06-22T17:46:39Z) - 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) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳(メタデータ) (2021-07-05T17:45:41Z) - Detailed Account of Complexity for Implementation of Some Gate-Based
Quantum Algorithms [55.41644538483948]
特に、状態準備および読み出しプロセスのような実装のいくつかのステップは、アルゴリズム自体の複雑さの側面を超越することができる。
本稿では、方程式の線形系と微分方程式の線形系を解くための量子アルゴリズムの完全な実装に関わる複雑性について述べる。
論文 参考訳(メタデータ) (2021-06-23T16:33:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。