論文の概要: Forging quantum data: classically defeating an IQP-based quantum test
- arxiv url: http://arxiv.org/abs/1912.05547v3
- Date: Wed, 6 Sep 2023 02:22:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-07 20:36:33.959733
- Title: Forging quantum data: classically defeating an IQP-based quantum test
- Title（参考訳）: 量子データの鍛造:古典的にiqpベースの量子テストを打ち破る
- Authors: Gregory D. Kahanamoku-Meyer
- Abstract要約: 古典的)証明器が量子であることを検証者に納得させる古典的アルゴリズムについて述べる。
キー抽出アルゴリズムは,実際に数百量子ビットの問題を解くのに有効であることを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recently, quantum computing experiments have for the first time exceeded the
capability of classical computers to perform certain computations -- a
milestone termed "quantum computational advantage." However, verifying the
output of the quantum device in these experiments required extremely large
classical computations. An exciting next step for demonstrating quantum
capability would be to implement tests of quantum computational advantage with
efficient classical verification, such that larger system sizes can be tested
and verified. One of the first proposals for an efficiently-verifiable test of
quantumness consists of hiding a secret classical bitstring inside a circuit of
the class IQP, in such a way that samples from the circuit's output
distribution are correlated with the secret (arXiv:0809.0847). The classical
hardness of this protocol has been supported by evidence that directly
simulating IQP circuits is hard, but the security of the protocol against other
(non-simulating) classical attacks has remained an open question. In this work
we demonstrate that the protocol is not secure against classical forgery. We
describe a classical algorithm that can not only convince the verifier that the
(classical) prover is quantum, but can in fact can extract the secret key
underlying a given protocol instance. Furthermore, we show that the key
extraction algorithm is efficient in practice for problem sizes of hundreds of
qubits. Finally, we provide an implementation of the algorithm, and give the
secret vector underlying the "$25 challenge" posted online by the authors of
the original paper.
- Abstract（参考訳）: 近年、量子コンピューティングの実験は、古典的なコンピュータが特定の計算を行う能力を上回るものとなり、これは「量子計算の優位性」と呼ばれるマイルストーンとなった。
しかし、これらの実験で量子デバイスの出力を検証するには、非常に大きな古典的計算が必要であった。
量子能力を示すためのエキサイティングな次のステップは、より大きなシステムサイズをテストし、検証できるように、効率的な古典的検証による量子計算の利点のテストを実装することである。
量子性の効率的な検証のための最初の提案の一つは、クラスIQPの回路内に秘密の古典的ビットストリングを隠して、回路の出力分布からのサンプルが秘密と相関する(arXiv:0809.0847)。
このプロトコルの古典的硬さは、IQP回路を直接シミュレートすることが難しいという証拠によって支持されているが、他の(非シミュレート的な)古典的攻撃に対するプロトコルのセキュリティは未解決のままである。
本研究では,このプロトコルが古典的偽造に対して安全でないことを実証する。
古典的な)証明器が量子であることを検証者に納得させるだけでなく、実際に与えられたプロトコルインスタンスの裏にある秘密鍵を抽出できる古典的なアルゴリズムを記述する。
さらに, 鍵抽出アルゴリズムは, 数百キュービットという問題に対して, 効果的であることを示す。
最後に,本アルゴリズムの実装と,原論文の著者によるオンライン投稿の「25ドルチャレンジ」の根底にある秘密ベクトルについて述べる。
関連論文リスト
- Single-Round Proofs of Quantumness from Knowledge Assumptions [41.94295877935867]
量子性の証明は、効率的な量子コンピュータが通過できる、効率よく検証可能な対話型テストである。
既存のシングルラウンドプロトコルは大きな量子回路を必要とするが、マルチラウンドプロトコルはより小さな回路を使用するが、実験的な中間回路測定を必要とする。
我々は、既存の知識仮定に基づいて、量子性の効率的なシングルラウンド証明を構築した。
論文 参考訳（メタデータ） (2024-05-24T17:33:10Z) - Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth [0.5188841610098435]
雑音の除去や非偏極化を行う任意のIQP回路の場合、出力分布は古典的コンピュータで効率的にサンプリング可能であることを示す。
我々は、IQP回路が対角ゲートの深い部分を持つという事実を利用して、ノイズが予測可能となり、回路内の絡み合いの大規模な分解を誘発する。
論文 参考訳（メタデータ） (2024-03-21T17:55:26Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Experimental Implementation of an Efficient Test of Quantumness [49.588006756321704]
量子性の試験は、古典的なユーザーが古典的でない振る舞いを示すかどうかを決定するために量子デバイスに課題を発行するプロトコルである。
最近の量子コンピュータにおけるこのようなテストの実装の試みは、効率的な検証を伴うインタラクティブな課題か、非効率的な(指数時間)検証を伴う非インタラクティブな課題に依存している。
論文 参考訳（メタデータ） (2022-09-28T18:00:04Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - An Optimized Quantum Implementation of ISD on Scalable Quantum Resources [2.274915755738124]
Prange の ISD アルゴリズムは量子コンピュータ上でより効率的に実装可能であることを示す。
我々は、古典的コプロセッサのアイデアを活用して、ハイブリッドな古典的量子トレードオフを設計する。
論文 参考訳（メタデータ） (2021-12-12T06:01:10Z) - Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
証明者と検証者の間の「相互作用」は、検証可能性と実装のギャップを埋めることができる。
イオントラップ量子コンピュータを用いた対話型量子アドバンストプロトコルの最初の実装を実演する。
論文 参考訳（メタデータ） (2021-12-09T19:00:00Z) - Depth-efficient proofs of quantumness [77.34726150561087]
量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。
本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
論文 参考訳（メタデータ） (2021-07-05T17:45:41Z) - Test of Quantumness with Small-Depth Quantum Circuits [1.90365714903665]
近年,LWE(Learning with error)の仮定に基づいて量子性テストを構築する方法が示されている。
このテストはいくつかの暗号アプリケーションにつながった。
本稿では,この量子性試験,および上述のすべての応用が,量子回路の非常に弱いクラスによって実際に実装可能であることを示す。
論文 参考訳（メタデータ） (2021-05-12T08:16:20Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。
悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。
我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
論文 参考訳（メタデータ） (2020-10-15T17:55:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。