論文の概要: The Space Just Above One Clean Qubit

• arxiv url: http://arxiv.org/abs/2410.08051v1
• Date: Thu, 10 Oct 2024 15:45:37 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-31 05:45:05.979730
• Title: The Space Just Above One Clean Qubit
• Title（参考訳）: 宇宙にはクリーンなクビットが1つある
• Authors: Dale Jacobs, Saeed Mehraban,
• Abstract要約: 本稿では、その制限にもかかわらず、$frac12$BQPはよく知られた量子計算を実行できることを示す。 $frac12$BQPは、瞬時量子多項式時間(IQP)をシミュレートし、Deutsch-Jozsa問題、Bernstein-Vazirani問題、Simonの問題、周期探索を解く。 我々は$frac12$BQPが$$$-Forrelationを解決できないと推測する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Consider the model of computation where we start with two halves of a $2n$-qubit maximally entangled state. We get to apply a universal quantum computation on one half, measure both halves at the end, and perform classical postprocessing. This model, which we call $\frac12$BQP, was defined in STOC 2017 [ABKM17] to capture the power of permutational computations on special input states. As observed in [ABKM17], this model can be viewed as a natural generalization of the one-clean-qubit model (DQC1) where we learn the content of a high entropy input state only after the computation is completed. An interesting open question is to characterize the power of this model, which seems to sit nontrivially between DQC1 and BQP. In this paper, we show that despite its limitations, this model can carry out many well-known quantum computations that are candidates for exponential speed-up over classical computations (and possibly DQC1). In particular, $\frac12$BQP can simulate Instantaneous Quantum Polynomial Time (IQP) and solve the Deutsch-Jozsa problem, Bernstein-Vazirani problem, Simon's problem, and period finding. As a consequence, $\frac12$BQP also solves Order Finding and Factoring outside of the oracle setting. Furthermore, $\frac12$BQP can solve Forrelation and the corresponding oracle problem given by Raz and Tal [RT22] to separate BQP and PH. We also study limitations of $\frac12$BQP and show that similarly to DQC1, $\frac12$BQP cannot distinguish between unitaries which are close in trace distance, then give an oracle separating $\frac12$BQP and BQP. Due to this limitation, $\frac12$BQP cannot obtain the quadratic speedup for unstructured search given by Grover's algorithm [Gro96]. We conjecture that $\frac12$BQP cannot solve $3$-Forrelation.
• Abstract（参考訳）: 2n$-qubit の最大絡み合い状態の 2 ハーフから始める計算モデルを考える。 半端に普遍的な量子計算を適用し、両半端を測り、古典的な後処理を実行する。 このモデルを$\frac12$BQPと呼び、STOC 2017[ABKM17]で定義した。 このモデルは, [ABKM17] で見られるように, 計算が完了した後にのみ高エントロピー入力状態の内容を学習する 1-clean-qubit model (DQC1) の自然な一般化と見なすことができる。 興味深いオープンな疑問は、DQC1 と BQP の間に非自明に置かれているように見えるこのモデルのパワーを特徴づけることである。 本稿では,その制限にもかかわらず,古典計算(DQC1)よりも指数的高速化の候補となる多くのよく知られた量子計算を行うことができることを示す。 特に$\frac12$BQP はインスタント量子多項式時間 (IQP) をシミュレートし、Deutsch-Jozsa問題、Bernstein-Vazirani問題、Simon の問題、周期探索を解くことができる。 その結果、$\frac12$BQPはオーラクル設定の外のオーダー検索とファクタリングも解決する。 さらに、$\frac12$BQP は、Forrelation と Raz と Tal [RT22] が与えるオラクル問題を BQP と PH を分離するために解くことができる。また、$\frac12$BQP の制限についても検討し、DQC1 と同様に、DQC1 と同様に、DQC1 と同様に、トレース距離が近いユニタリを区別できないことを示すとともに、$\frac12$BQP と BQP を分離するオラクルを与える。 この制限により、$\frac12$BQPはGroverのアルゴリズム[Gro96]によって与えられる非構造化探索の二次的なスピードアップを得ることができない。 我々は$\frac12$BQPが$$$-Forrelationを解決できないと推測する。

関連論文リスト

• Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
  乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。 結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
  論文  参考訳（メタデータ） (2024-11-04T00:39:52Z)
• Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
  量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。 驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。 約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
  論文  参考訳（メタデータ） (2024-11-01T18:00:56Z)
• 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)
• Kernelized Normalizing Constant Estimation: Bridging Bayesian Quadrature and Bayesian Optimization [51.533164528799084]
  小さい相対誤差内で正規化定数を推定するために、難易度は$lambda$の値に依存する。 関数評価がノイズである場合でも,このパターンは真であることがわかった。
  論文  参考訳（メタデータ） (2024-01-11T07:45:09Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  浅量子回路の計算能力と古典計算の組合せを包括的に評価する。 いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
  論文  参考訳（メタデータ） (2022-10-12T17:54:02Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  量子計算の2つのモデル: CQ_dとQC_d。 CQ_dは、d-d-deepth量子コンピュータのシナリオを何度も捉え、QC_dは測定ベースの量子計算に類似している。 CQ_dとQC_dの類似性にもかかわらず、2つのモデルは本質的にはCQ_d $nsubseteq$QC_dとQC_d $nsubseteq$CQ_dである。
  論文  参考訳（メタデータ） (2022-01-06T03:10:53Z)
• Quantum Linear Algorithm for Edit Distance Using the Word QRAM Model [0.0]
  2次時間分解可能問題のビット並列性を、係数$n$でスピードアップできる量子アルゴリズムに変換する方法を示す。 まず、Myers (J. ACM, 1999) の有名な$O(n2/w)$ time bit-parallel アルゴリズムが算術+演算なしで動作するように調整可能であることを示す。
  論文  参考訳（メタデータ） (2021-12-24T09:26:55Z)
• Classical algorithms for Forrelation [2.624902795082451]
  1対の$n$-bit Boolean 関数 $f$ と $g$ が与えられたとき、$f$ と $g$ のフーリエ変換の間の相関を推定する。 この問題は、クエリの複雑さの観点から最大の量子スピードアップをもたらすことが知られている。 グラフに基づく回帰問題は、任意の二部グラフに対して時間$O(n)$で解けることを示す。
  論文  参考訳（メタデータ） (2021-02-13T17:25:41Z)
• Variational Quantum Linear Solver [0.3774866290142281]
  本稿では,線形系を線形に解くための量子古典的ハイブリッドアルゴリズムを提案する。 リゲッティの量子コンピュータを用いて,250Times250$までの大きさの非自明な問題を数値的に解く。
  論文  参考訳（メタデータ） (2019-09-12T17:28:09Z)

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

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