論文の概要: Post-Quantum Zero-Knowledge with Space-Bounded Simulation
- arxiv url: http://arxiv.org/abs/2210.06093v1
- Date: Wed, 12 Oct 2022 11:13:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-22 19:43:23.589684
- Title: Post-Quantum Zero-Knowledge with Space-Bounded Simulation
- Title（参考訳）: 空間境界シミュレーションによる量子後ゼロ知識
- Authors: Prabhanjan Ananth and Alex B. Grilo
- Abstract要約: 近距離量子デバイスとより互換性のある,量子後ゼロ知識の詳細な概念を導入する。
対数量子空間 $s$ と古典空間を持つ検証器に対しては、$f(s)=2s$ に対して$(s,f)$-空間有界 QZK が得られることを示す。
超対数量子空間$s$の検証器について、量子後一方向の存在を仮定すると、完全に黒の$(s,f)$空間有界QZKプロトコルが示される。
- 参考スコア（独自算出の注目度）: 8.69082943773532
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The traditional definition of quantum zero-knowledge stipulates that the
knowledge gained by any quantum polynomial-time verifier in an interactive
protocol can be simulated by a quantum polynomial-time algorithm. One drawback
of this definition is that it allows the simulator to consume significantly
more computational resources than the verifier. We argue that this drawback
renders the existing notion of quantum zero-knowledge not viable for certain
settings, especially when dealing with near-term quantum devices.
In this work, we initiate a fine-grained notion of post-quantum
zero-knowledge that is more compatible with near-term quantum devices. We
introduce the notion of $(s,f)$ space-bounded quantum zero-knowledge. In this
new notion, we require that an $s$-qubit malicious verifier can be simulated by
a quantum polynomial-time algorithm that uses at most $f(s)$-qubits, for some
function $f(\cdot)$, and no restriction on the amount of the classical memory
consumed by either the verifier or the simulator. We explore this notion and
establish both positive and negative results:
- For verifiers with logarithmic quantum space $s$ and (arbitrary) polynomial
classical space, we show that $(s,f)$-space-bounded QZK, for $f(s)=2s$, can be
achieved based on the existence of post-quantum one-way functions. Moreover,
our protocol runs in constant rounds.
- For verifiers with super-logarithmic quantum space $s$, assuming the
existence of post-quantum secure one-way functions, we show that
$(s,f)$-space-bounded QZK protocols, with fully black-box simulation (classical
analogue of black-box simulation) can only be achieved for languages in BQP.
- Abstract（参考訳）: 従来のゼロ知識の定義では、対話プロトコルにおける任意の量子多項式時間検証器によって得られる知識は、量子多項式時間アルゴリズムによってシミュレートできる。
この定義の欠点は、シミュレータが検証者よりもはるかに多くの計算資源を消費できることである。
この欠点は、量子ゼロ知識という既存の概念が、特に短期的な量子デバイスを扱う場合、特定の設定では不可能であることを示している。
本研究では、近距離量子デバイスとより相性が良い量子後ゼロ知識のきめ細かい概念を開始する。
我々は、$(s,f)$空間有界量子零知識の概念を導入する。
この新たな概念では、ある関数$f(\cdot)$に対して、少なくとも$f(s)$-qubitsを使用する量子多項式時間アルゴリズムによって、$s$-qubitの悪意のある検証器をシミュレートし、検証器またはシミュレータが消費する古典的メモリの量を制限することを要求する。
対数量子空間 $s$ と (arbitrary) 多項式古典空間を持つ検証器に対して、$(s,f)$-space-bounded QZK, for $f(s)=2s$ がポスト量子片道函数の存在に基づいて達成可能であることを示す。
さらに、プロトコルは一定のラウンドで動作します。
- 超対数量子空間を持つ検証者が$s$ であり、量子後セキュアな一方向関数の存在を仮定すると、完全にブラックボックスシミュレーション(ブラックボックスシミュレーションの古典的類似物)を持つ$(s,f)$-space-bounded qzkプロトコルはbqpの言語でしか実現できない。
関連論文リスト
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳（メタデータ） (2024-08-22T08:21:28Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - A Cryptographic Perspective on the Verifiability of Quantum Advantage [5.857929080874288]
本稿では,暗号的観点からの量子優位性の検証について検討する。
量子優位性と暗号および複雑性プリミティブの妥当性の強い関係を確立する。
我々の研究は、検証可能な量子長所を求めることが量子暗号の応用につながる可能性を示唆している。
論文 参考訳（メタデータ） (2023-10-23T00:31:51Z) - Fundamental causal bounds of quantum random access memories [13.19534468575575]
因果性に基づく高速量子メモリの本質的境界について検討する。
QRAMは1次元で$mathcalO(107)$論理量子ビット、様々な2次元アーキテクチャで$mathcalO(1015)$から$mathcalO(1020)$、そして3次元で$mathcalO(1024)$に対応可能であることを示す。
論文 参考訳（メタデータ） (2023-07-25T12:40:48Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
証明者と検証者の間の「相互作用」は、検証可能性と実装のギャップを埋めることができる。
イオントラップ量子コンピュータを用いた対話型量子アドバンストプロトコルの最初の実装を実演する。
論文 参考訳（メタデータ） (2021-12-09T19:00:00Z) - Calculation of generating function in many-body systems with quantum
computers: technical challenges and use in hybrid quantum-classical methods [0.0]
ハミルトニアン$H$の生成関数は$F(t)=langle e-itHrangle$と定義される。
量子多体問題の解法として,この関数の情報を古典計算機で後続的に用いる方法を示す。
論文 参考訳（メタデータ） (2021-04-16T15:44:27Z) - A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds [12.525959293825318]
我々は,統計音性およびブラックボックス$epsilon$-zero-knowledgeを満たすNPのラウンド・インタラクティブ証明を構築した。
我々の研究の核心は、シミュレーターが悪意のある検証者のコミットメッセージを抽出できる新しい量子巻き戻し技術である。
論文 参考訳（メタデータ） (2020-11-05T05:40:05Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
古典的アリス(Alice)と量子的ボブ(Quantum Bob)が古典的なチャネルを通してのみ通信できるような設定を考える。
悪質な量子逆数の場合,ブラックボックスシミュレーションを用いた2次元量子関数を実現することは,一般に不可能であることを示す。
我々は、QMA関係Rの古典的量子知識(PoQK)プロトコルを入力として、古典的当事者によって検証可能なRのゼロ知識PoQKを出力するコンパイラを提供する。
論文 参考訳（メタデータ） (2020-10-15T17:55:31Z) - Quantum advantage for computations with limited space [6.327095331866255]
我々は、入力が読み取り専用メモリであり、1(qu)ビットしか計算できない空間制限型計算を考える。
我々は、量子回路による3ドル、4ドル、5ドル、6ドルという計算を、カスタム2量子ゲートを利用して実験的に実証した。
論文 参考訳（メタデータ） (2020-08-14T17:31:12Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。