論文の概要: Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games
- arxiv url: http://arxiv.org/abs/2609.38060v1
- Date: Tue, 29 Sep 2026 17:27:09 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-30 21:28:47.78474
- Title: Classical Verification of Quantum Computation with Quasilinear Resources, from Compiled Nonlocal Games
- Title（参考訳）: コンパイルされた非局所ゲームからの準線形資源を用いた量子計算の古典的検証
- Abstract要約: 計算自己検証は、単一の計算で有界な証明子の量子レジスタ上の古典的な検証コマンドを与える。
このフレームワークを用いて、回路モデルにおける準線形全リソース要求によるBQPの最初の引数システムを構築する。
これは、証明者の量子状態を証明するための新しい計算自己テストを構築することで達成される。
- 参考スコア（独自算出の注目度）: 0.05735035463793008
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Computational self-testing gives a classical verifier command over the quantum register of a single computationally bounded prover. We use this framework to construct the first argument system for BQP with quasilinear total resource requirements in the circuit model. Our argument system is based on the learning with errors (LWE) assumption and requires total resources of $O(\mathrm{poly}(λ, \log g)\cdot g)$ for delegating a circuit with $g$ gates, where $λ$ is the LWE security parameter. This is achieved by constructing a new computational self-test for certifying the prover's quantum state and using it to dequantize the efficient verification protocol of Broadbent (ToC 2018). Specifically, this self-test enables the verifiable, random remote state preparation of tensor product states of the single-qubit Clifford observables $σ_X, σ_Y, σ_Z, (σ_Y-σ_X)/\sqrt{2}$ and $(σ_Y+σ_X)/\sqrt{2}$, with constant robustness: the verification error is independent of the number of prepared qubits. This approach was first proposed by Coladangelo et al. (ToC 2024) in the multi-prover setting. We replicate their result in the single-prover setting by applying the compiler proposed by Kalai et al. (STOC 2023)---which turns any nonlocal game into a single-prover argument system---to a modified version of their self-test.
- Abstract（参考訳）: 計算自己検証は、単一の計算で有界な証明子の量子レジスタ上の古典的な検証コマンドを与える。
このフレームワークを用いて、回路モデルにおける準線形全リソース要求によるBQPの最初の引数システムを構築する。
我々の議論システムは、誤り(LWE)を仮定した学習に基づいており、回路を$g$ゲートで委譲するためには、$O(\mathrm{poly}(λ, \log g)\cdot g)$の総リソースを必要とする。
これは、証明者の量子状態を証明し、Broadbent(ToC 2018)の効率的な検証プロトコルを復号化する新しい計算自己テストを構築することで達成される。
具体的には、この自己検定により、単一の量子ビット Clifford 観測可能な $σ_X, σ_Y, σ_Z, (σ_Y-σ_X)/\sqrt{2}$ と $(σ_Y+σ_X)/\sqrt{2}$ のテンソル積状態の検証可能なランダムなリモート状態の準備が可能となる。
このアプローチは Coladangelo et al (ToC 2024) によってマルチプロデューサ設定で最初に提案された。
我々は、Kalaiらによって提案されたコンパイラー(STOC 2023)を応用し、それらの結果をシングルプロファイラで再現する。
関連論文リスト
- SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant [79.24089819400126]
Subsampled TurboQuant (SSTQ) は、オーバーコンプリートな等幅のタイトフレーム、座標サブサンプリング、プライバシ対応量子化を組み合わせたフレームワークである。
SSTQは平均2乗誤差スケーリングを実現し、クライアントあたり$lceil log N il + b$ bitsを使用する。
また、コードブックに依存したMSEスケーリングを$O(4b)$から$O(2b)$に削減する、プライバシを意識したコードブックの目的も導出します。
論文 参考訳（メタデータ） (2026-08-05T17:51:25Z) - Quantum Occam Learning: Sample-Supported Expressibility for Circuit-Based Quantum Learning [0.3277163122167433]
有限サイズの量子回路によって生成される量子データに対する情報理論オッカム理論を開発した。
M$コピーで、G$-gate近似エラーと統計的ペナルティを学習できる。
我々のフレームワークは、有界回路の複雑さを量子機械学習のモデル選択原理に変える。
論文 参考訳（メタデータ） (2026-06-10T15:28:36Z) - A Modular Approach to Succinct Arguments for QMA [17.20526790095253]
我々は、QMAの簡潔な議論の暗号的基礎を広げる新しいフレームワークを開発する。
特に、LWEの硬さに依存しないQMAの最初の簡潔で古典的に検証可能な引数システムを得る。
我々のコンパイラはZhang(QCrypt 25)の量子剛性に基づく通信圧縮技術を拡張している
論文 参考訳（メタデータ） (2026-06-03T21:38:23Z) - Adiabatic Quantum Phase Estimation [47.3103723337301]
量子位相推定(QPE)は、ハミルトニアンの固有値をハイゼンベルク制限時間$T= (1/)$の精度で推定する中心的アルゴリズムプリミティブである。
QPEの標準ゲートベースの実装は、深く制御された時間進化回路を必要とし、アナログハードウェアに固有のものではない。
最適ハイゼンベルク制限スケーリング$T = Oleft( frac1 logleft(-1right)right)$を両精度で達成するQPEのための単純な断熱プロトコルを提案する。
論文 参考訳（メタデータ） (2026-05-21T17:31:36Z) - Quantum Causal Discovery via Amplitude Estimation of Kullback-Leibler Divergence [0.0]
本稿では,クリッピングされた対数密度比を振幅推定として符号化した量子アルゴリズムQKLA(Quantum Kullback-Leibler Amplitude Estimation)を提案する。
QKLAは2次精度の改善を実現し、$mathcalO((L/)log (1/)$クエリのみを必要とする。
階層ごとの条件付きオーラルアクセスとCI決定のマージン仮定の下で、PCアルゴリズムの化合物にこの推定器を埋め込み、$widetilde (1/(L)にする。
論文 参考訳（メタデータ） (2026-04-25T21:46:28Z) - Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Classical Verification of Quantum Computations in Linear Time [2.3465488122819123]
複雑度$O(poly(kappa)|C|)$という,既存のプロトコルよりもはるかに高速なCVQCプロトコルを提供する。
我々のプロトコルは、ノイズの多いトラップドアの爪のない関数の存在を前提として、量子ランダムオラクルモデル [arXiv:1008.0931] において安全である。
また、$|+thetarangle=frac1sqrt2(|0rangle+eithetapi/4|1rangle)の状態に対する新しい古典的なチャネルリモート状態準備プロトコルも提供します。
論文 参考訳（メタデータ） (2022-02-28T18:05:53Z) - Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。
最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
論文 参考訳（メタデータ） (2020-07-23T10:50:42Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。
格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。
NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
論文 参考訳（メタデータ） (2020-02-25T19:18:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。