論文の概要: Space-Bounded Unitary Quantum Computation with Postselection

• arxiv url: http://arxiv.org/abs/2206.15122v2
• Date: Tue, 13 Sep 2022 06:02:54 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-07 04:51:17.730994
• Title: Space-Bounded Unitary Quantum Computation with Postselection
• Title（参考訳）: 空間境界ユニタリ量子計算とポストセレクション
• Authors: Seiichiro Tani
• Abstract要約: 本稿では,空間境界量子計算における中間的ポストセレクションと測定をポストセレクションで除去できることを示す。 応用として、ポストセレクション付き有界エラー空間有界1クリーンキュービット計算(DQC1)は、非有界エラー空間有界確率計算と等価であることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Space-bounded computation has been a central topic in classical and quantum complexity theory. In the quantum case, every elementary gate must be unitary. This restriction makes it unclear whether the power of space-bounded computation changes by allowing intermediate measurement. In the bounded error case, Fefferman and Remscrim [STOC 2021, pp.1343--1356] and Girish, Raz and Zhan~[ICALP 2021, pp.73:1--73:20] recently provided the break-through results that the power does not change. This paper shows that a similar result holds for space-bounded quantum computation with postselection. Namely, it is proved possible to eliminate intermediate postselections and measurements in the space-bounded quantum computation in the bounded-error setting. Our result strengthens the recent result by Le Gall, Nishimura and Yakaryilmaz~[TQC 2021, pp.10:1--10:17] that logarithmic-space bounded-error quantum computation with intermediate postselections and measurements is equivalent in computational power to logarithmic-space unbounded-error probabilistic computation. As an application, it is shown that bounded-error space-bounded one-clean qubit computation (DQC1) with postselection is equivalent in computational power to unbounded-error space-bounded probabilistic computation, and the computational supremacy of the bounded-error space-bounded DQC1 is interpreted in complexity-theoretic terms.
• Abstract（参考訳）: 空間有界計算は古典的および量子複雑性理論において中心的な話題となっている。 量子の場合、すべての基本ゲートはユニタリでなければならない。 この制限により、中間測定を行うことで空間境界計算のパワーが変化するかどうかが明らかになる。 境界誤差の場合、Fefferman and Remscrim [STOC 2021, pp.1343--1356] と Girish, Raz and Zhan~ [ICALP 2021, pp.73:1--73:20] は、電力が変化しないブレークスルー結果を提供した。 本稿では,空間有界量子計算とポストセレクションの類似結果を示す。 すなわち、空間境界量子計算における中間的ポストセレクションと測定を、有界エラー設定で排除できることが証明されている。 この結果は, 対数空間境界誤差量子計算と中間ポストセレクション, 測定値が対数空間非有界誤差確率計算と等価であることを示す。 その結果, 有界誤差空間境界付き一クリーン量子ビット計算(dqc1)は非有界誤差空間境界確率計算と等価であり, 有界誤差空間境界付きdqc1の計算超越性は複雑性論的に解釈できることがわかった。

関連論文リスト

• The Space-Time Cost of Purifying Quantum Computations [12.640283469603357]
  一般的な量子計算は、ユニタリ演算と測定によって構成される。 中間量子測定は計算の終了まで遅延することができ、結果として等価な純粋に単項計算となる。 中間測定を除去する「ブラックボックス」変換は、空間または時間の両方を著しく爆発させなければならないことを示す。
  論文  参考訳（メタデータ） (2024-01-15T21:38:02Z)
• Dilation theorem via Schr\"odingerisation, with applications to the quantum simulation of differential equations [29.171574903651283]
  作用素論におけるナジーのユニタリ拡張定理は、縮約をユニタリ作用素に拡張する可能性を主張する。 本研究では,最近考案されたSchr"odingerisationアプローチの実用性を示す。
  論文  参考訳（メタデータ） (2023-09-28T08:55:43Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Validation tests of GBS quantum computers give evidence for quantum advantage with a decoherent target [62.997667081978825]
  複数モードデータの検証に指紋としてグループカウント確率の正P位相空間シミュレーションを用いる。 偽データを解き放つ方法を示し、これを古典的なカウントアルゴリズムに適用する。
  論文  参考訳（メタデータ） (2022-11-07T12:00:45Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Quantum Logarithmic Space and Post-selection [0.4588028371034406]
  ポストセレクション(Post-Selection)は、アーロンソンによって量子複雑性理論の分野に導入された影響力ある概念である(Royal Society A, 2005 の論文)。 我々の主な結果は、$sf PostBQL=$、すなわち、選択後(sf PostBQL$)で境界付きエラー(polynomial-time)対数空間量子アルゴリズムによって解決できる問題のクラスを示す。 また、$sf$は時間制限のない有界誤差対数空間量子アルゴリズムによって解くことができる問題のクラスと一致することを示す。
  論文  参考訳（メタデータ） (2021-05-06T14:02:01Z)
• Sampling and the complexity of nature [0.0]
  量子サンプリングアルゴリズムの複雑性理論と物理基礎について検討する。 量子サンプリングデバイスをテストしたり、検証したりできる状況と状況について、光を当てています。 テーゼの包括的なテーマは、経路間の破壊的な干渉によって生じる量子サイン問題である。
  論文  参考訳（メタデータ） (2020-12-14T19:35:27Z)
• Quantum advantage for computations with limited space [6.327095331866255]
  我々は、入力が読み取り専用メモリであり、1(qu)ビットしか計算できない空間制限型計算を考える。 我々は、量子回路による3ドル、4ドル、5ドル、6ドルという計算を、カスタム2量子ゲートを利用して実験的に実証した。
  論文  参考訳（メタデータ） (2020-08-14T17:31:12Z)
• The role of boundary conditions in quantum computations of scattering observables [58.720142291102135]
  量子コンピューティングは、量子色力学のような強い相互作用する場の理論を物理的時間進化でシミュレートする機会を与えるかもしれない。 現在の計算と同様に、量子計算戦略は依然として有限のシステムサイズに制限を必要とする。 我々は、ミンコフスキー符号量1+1ドルの体積効果を定量化し、これらが体系的不確実性の重要な源であることを示す。
  論文  参考訳（メタデータ） (2020-07-01T17:43:11Z)
• Eliminating Intermediate Measurements in Space-Bounded Quantum Computation [0.0]
  量子計算の終端まで測定を遅延させることは、アシラリー量子ビットの数を増大させることなく可能であることを示す。 このアプローチの重要な構成要素は、多くの標準的な線形代数的問題のよく調和したバージョンが、古典的なコンピュータよりも少ない空間で量子コンピュータによって解決されることを示すことである。
  論文  参考訳（メタデータ） (2020-06-05T16:05:49Z)

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

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