論文の概要: Classical Verification of Quantum Computations in Linear Time
- arxiv url: http://arxiv.org/abs/2202.13997v5
- Date: Sun, 2 Jun 2024 14:32:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-06 16:52:40.884676
- Title: Classical Verification of Quantum Computations in Linear Time
- Title（参考訳）: 線形時間における量子計算の古典的検証
- Authors: Jiayu Zhang,
- Abstract要約: 複雑度$O(poly(kappa)|C|)$という,既存のプロトコルよりもはるかに高速なCVQCプロトコルを提供する。
我々のプロトコルは、ノイズの多いトラップドアの爪のない関数の存在を前提として、量子ランダムオラクルモデル [arXiv:1008.0931] において安全である。
また、$|+thetarangle=frac1sqrt2(|0rangle+eithetapi/4|1rangle)の状態に対する新しい古典的なチャネルリモート状態準備プロトコルも提供します。
- 参考スコア（独自算出の注目度）: 2.3465488122819123
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In the quantum computation verification problem, a quantum server wants to convince a client that the output of evaluating a quantum circuit $C$ is some result that it claims. This problem is considered very important both theoretically and practically in quantum computation [arXiv:1709.06984], [arXiv:1704.04487], [arXiv:1209.0449]. The client is considered to be limited in computational power, and one desirable property is that the client can be completely classical, which leads to the classical verification of quantum computation (CVQC) problem. In terms of the total time complexity, the fastest single-server CVQC protocol so far has complexity $O(poly(\kappa)|C|^3)$ where $|C|$ is the size of the circuit to be verified and $\kappa$ is the security parameter, given by Mahadev [arXiv:1804.01082]. In this work, by developing new techniques, we give a new CVQC protocol with complexity $O(poly(\kappa)|C|)$, which is significantly faster than existing protocols. Our protocol is secure in the quantum random oracle model [arXiv:1008.0931] assuming the existence of noisy trapdoor claw-free functions [arXiv:1804.00640], which are both extensively used assumptions in quantum cryptography. Along the way, we also give a new classical channel remote state preparation protocol for states in $\{|+_\theta\rangle=\frac{1}{\sqrt{2}}(|0\rangle+e^{i\theta\pi/4}|1\rangle):\theta\in \{0,1\cdots 7\}\}$, another basic primitive in quantum cryptography. Our protocol allows for parallel verifiable preparation of $L$ independently random states in this form (up to a constant overall error and a possibly unbounded server-side simulator), and runs in only $O(poly(\kappa)L)$ time and constant rounds; for comparison, existing works (even for possibly simpler state families) all require very large or unestimated time and round complexities [arXiv:1904.06320][arXiv:1904.06303][arXiv:2201.13445][arXiv:2201.13430].
- Abstract（参考訳）: 量子計算検証問題において、量子サーバは、量子回路の$C$を評価する出力が、それが主張する結果であるということをクライアントに納得させようとする。
この問題は、量子計算 [arXiv:1709.06984], [arXiv:1704.04487], [arXiv:1209.0449] において理論的にも実用的にも非常に重要であると考えられている。
クライアントは計算能力に制限があると考えられており、クライアントは完全に古典的になり、量子計算(CVQC)問題の古典的検証に繋がる。
合計時間複雑性に関しては、これまで最速のシングルサーバCVQCプロトコルは、$O(poly(\kappa)|C|^3)$であり、$|C|$は検証対象回路のサイズであり、$\kappa$はMahadev [arXiv:1804.01082]によって与えられるセキュリティパラメータである。
本研究では,新しい手法を開発することにより,既存のプロトコルよりもはるかに高速な,複雑さの$O(poly(\kappa)|C|)$のCVQCプロトコルを提供する。
我々のプロトコルは、量子暗号において広く使われているノイズの多いトラップドアの爪のない関数 [arXiv:1804.00640] の存在を前提として、量子ランダムオラクルモデル [arXiv:1008.0931] において安全である。
その過程では、$\{|+_\theta\rangle=\frac{1}{\sqrt{2}}(|0\rangle+e^{i\theta\pi/4}|1\rangle):\theta\in \{0,1\cdots 7\}\}$という、量子暗号における別の基本的なプリミティブに対して、新しい古典的なチャネルリモート状態準備プロトコルも提供します。
我々のプロトコルは、この形式で独立に$L$のランダムな状態を並列で作成することを可能にし、O(poly(\kappa)L)$時間と定数のラウンドでしか実行できない。比較すると、既存の作業(おそらくはより単純な状態のファミリーでも)は、非常に大きな時間とラウンドの複雑さを必要とする[arXiv:1904.06320][arXiv:1904.06303][arXiv:2201.13445][arXiv:2201.13445]][arXiv:2201.13430]]]]。
関連論文リスト
- Multi-level quantum signal processing with applications to ground state preparation using fast-forwarded Hamiltonian evolution [0.8359711817610189]
大きなスペクトル半径を持つハミルトンの$H$の基底状態の合成は多くの領域で応用されている。
高速転送機能を利用するマルチレベル量子信号処理(QSP)ベースのアルゴリズムを開発した。
論文 参考訳（メタデータ） (2024-06-04T08:09:51Z) - A Unifying Quantum Speed Limit For Time-Independent Hamiltonian Evolution [0.3314882635954752]
マンデルスタム-タム境界は、あるパラメータ上でリー-チャウ境界を最適化することで得られることを示す。
ヒルベルト空間の次元が $lesssim 2000$ であれば、$p$ に最適化された統一境界は数分で正確に計算できる。
論文 参考訳（メタデータ） (2023-10-13T01:52:04Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Non-local computation of quantum circuits with small light cones [0.0]
ポートベースのテレポーテーションは、一度に少数の量子ビットでのみ行われる場合、はるかに少ない絡み合いになる。
我々は、プロトコルの絡み合いコストが既知のプロトコルよりも良くスケールする、明示的なユニタリのクラスを提供する。
論文 参考訳（メタデータ） (2022-03-18T18:00:06Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。
最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
論文 参考訳（メタデータ） (2020-07-23T10:50:42Z) - Security Limitations of Classical-Client Delegated Quantum Computing [54.28005879611532]
クライアントは、古典的なチャネルを使用して量子状態をリモートで準備する。
サブモジュールとして$RSP_CC$を採用することで生じるプライバシ損失は、不明である。
特定の$RSP_CC$プロトコルは、少なくともいくつかのコンテキストにおいて量子チャネルを置き換えることができることを示す。
論文 参考訳（メタデータ） (2020-07-03T13:15:13Z) - Succinct Blind Quantum Computation Using a Random Oracle [0.8702432681310399]
我々は新しい普遍的な盲点量子計算プロトコルを提供する。
プロトコルの最初のフェーズは簡潔であり、その複雑さは回路サイズとは無関係である。
論文 参考訳（メタデータ） (2020-04-27T07:47:11Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z) - Communication Cost of Quantum Processes [49.281159740373326]
分散コンピューティングにおける一般的なシナリオは、リモートコンピュータ上で計算を実行するようサーバに要求するクライアントである。
重要な問題は、所望の計算を指定するのに必要な最小限の通信量を決定することである。
クライアントが選択した量子処理を正確に実行するために、サーバが必要とする(古典的および量子的)通信の総量を分析する。
論文 参考訳（メタデータ） (2020-02-17T08:51:42Z) - Variational Quantum Linear Solver [0.3774866290142281]
本稿では,線形系を線形に解くための量子古典的ハイブリッドアルゴリズムを提案する。
リゲッティの量子コンピュータを用いて,250Times250$までの大きさの非自明な問題を数値的に解く。
論文 参考訳（メタデータ） (2019-09-12T17:28:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。