論文の概要: Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection

• arxiv url: http://arxiv.org/abs/2206.05434v4
• Date: Tue, 21 Jan 2025 06:19:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-23 13:28:37.122685
• Title: Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection
• Title（参考訳）: Rewindable Quantum Computation and its Equival to Cloning and Adaptive Postselection (特集:「量子コンピューティング」)
• Authors: Ryo Hiromasa, Akihiro Mizutani, Yuki Takeuchi, Seiichiro Tani,
• Abstract要約: sf PostBQP$の任意の問題は、確率的に1に近いポストセレクションのみによって解決できることを示す。 また、巻き戻し可能な瞬時量子時間回路は、任意の問題を$sf PP$で解くことができることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: We define rewinding operators that invert quantum measurements. Then, we define complexity classes ${\sf RwBQP}$, ${\sf CBQP}$, and ${\sf AdPostBQP}$ as sets of decision problems solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that ${\sf BPP}^{\sf PP}\subseteq{\sf RwBQP}={\sf CBQP}={\sf AdPostBQP}\subseteq{\sf PSPACE}$. As a byproduct of this result, we show that any problem in ${\sf PostBQP}$ can be solved with only postselections of events that occur with probabilities polynomially close to one. Under the strongly believed assumption that ${\sf BQP}\nsupseteq{\sf SZK}$, or the shortest independent vectors problem cannot be efficiently solved with quantum computers, we also show that a single rewinding operator is sufficient to achieve tasks that are intractable for quantum computation. Finally, we show that rewindable Clifford circuits remain classically simulatable, but rewindable instantaneous quantum polynomial time circuits can solve any problem in ${\sf PP}$.
• Abstract（参考訳）: 量子測定を反転させる巻き戻し演算子を定義する。 次に、複雑性クラス ${\sf RwBQP}$, ${\sf CBQP}$, ${\sf AdPostBQP}$ を多項式サイズの量子回路で解ける決定問題の集合として定義する。 主な結果は、${\sf BPP}^{\sf PP}\subseteq{\sf RwBQP}={\sf CBQP}={\sf AdPostBQP}\subseteq{\sf PSPACE}$である。 この結果の副産物として、${\sf PostBQP}$ の任意の問題は、確率が 1 に多項式的に近い場合に起こる事象のポストセレクションでのみ解決できることを示す。 量子コンピュータでは、${\sf BQP}\nsupseteq{\sf SZK}$あるいは最も短い独立ベクトル問題を効率的に解けないという強い信念のもと、単一の巻き戻し演算子が量子計算に難航するタスクを達成するのに十分であることを示す。 最後に、巻き戻し可能なクリフォード回路は古典的にシミュレート可能であるが、巻き戻し可能な瞬時量子多項式時間回路は${\sf PP}$の任意の問題を解くことができることを示す。

関連論文リスト

• Oracle Separations for the Quantum-Classical Polynomial Hierarchy [0.0]
  量子古典的階層 QCPH について検討する。これは、交互古典的量子化器の定数数で解ける言語のクラスである。 我々は、量子アルゴリズムに新しい切り換え補題を与えるが、これは独立した関心を持つかもしれない。
  論文  参考訳（メタデータ） (2024-10-24T18:12:03Z)
• Parallel Quantum Signal Processing Via Polynomial Factorization [3.1981483719988235]
  量子並列信号処理アルゴリズムを開発した。 我々のアルゴリズムは、$texttr (P(rho)$ over $k$の計算を並列化し、クエリの深さを$d/k$に減らし、QSPの時間空間トレードオフのファミリを可能にする。 これにより、量子コンピュータに適した特性推定が可能となり、$O(textpoly(d) 2(k) )$ で測定数を増やすことで実現される。
  論文  参考訳（メタデータ） (2024-09-27T17:54:30Z)
• Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians [0.0]
  非適応型量子PCPは、証明クエリ数が一定である場合に適応型量子PCPをシミュレートできることを示す。 また、ある量子PCPステートメントが偽であるような(量子)オラクルが存在することも示している。
  論文  参考訳（メタデータ） (2024-03-07T19:00:06Z)
• The Power of Lorentz Quantum Computer [6.9754404995027794]
  本稿では,最近提案されたローレンツ量子コンピュータ(LQC)の,従来の量子コンピュータと比較して優れた性能を示す。 計算複雑性クラス$text Psharp textP$を導入し、複雑性クラス$text Psharp textP$と等価性を実証する。 Aaronsonが提案したポストセレクションによる量子コンピューティングはLQCで効率的にシミュレートできるが、その逆ではない。
  論文  参考訳（メタデータ） (2024-03-07T03:00:09Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。 我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
  論文  参考訳（メタデータ） (2024-01-17T18:59:38Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
  我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。 最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
  論文  参考訳（メタデータ） (2020-07-23T10:50:42Z)
• Variational Quantum Linear Solver [0.3774866290142281]
  本稿では,線形系を線形に解くための量子古典的ハイブリッドアルゴリズムを提案する。 リゲッティの量子コンピュータを用いて,250Times250$までの大きさの非自明な問題を数値的に解く。
  論文  参考訳（メタデータ） (2019-09-12T17:28:09Z)

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

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