論文の概要: Post-Quantum Zero Knowledge, Revisited (or: How to Do Quantum Rewinding
Undetectably)
- arxiv url: http://arxiv.org/abs/2111.12257v1
- Date: Wed, 24 Nov 2021 04:11:56 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-07 00:15:02.058380
- Title: Post-Quantum Zero Knowledge, Revisited (or: How to Do Quantum Rewinding
Undetectably)
- Title（参考訳）: 量子化後ゼロ知識、再訪(または:量子再巻き戻しを検知不能に行う方法)
- Authors: Alex Lombardi and Fermi Ma and Nicholas Spooner
- Abstract要約: 我々は、内部状態を乱すことなく、それを巻き戻し、量子敵から情報を抽出する方法を示す。
我々は、グラフ非同型に対するGoldreich-Micali-WigdersonプロトコルとNPに対するFeigeShamirプロトコルが、量子敵に対するゼロ知識であることを証明した。
- 参考スコア（独自算出の注目度）: 7.740250954954346
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A major difficulty in quantum rewinding is the fact that measurement is
destructive: extracting information from a quantum state irreversibly changes
it. This is especially problematic in the context of zero-knowledge simulation,
where preserving the adversary's state is essential.
In this work, we develop new techniques for quantum rewinding in the context
of extraction and zero-knowledge simulation:
(1) We show how to extract information from a quantum adversary by rewinding
it without disturbing its internal state. We use this technique to prove that
important interactive protocols, such as the Goldreich-Micali-Wigderson
protocol for graph non-isomorphism and the Feige-Shamir protocol for NP, are
zero-knowledge against quantum adversaries.
(2) We prove that the Goldreich-Kahan protocol for NP is post-quantum zero
knowledge using a simulator that can be seen as a natural quantum extension of
the classical simulator.
Our results achieve (constant-round) black-box zero-knowledge with negligible
simulation error, appearing to contradict a recent impossibility result due to
Chia-Chung-Liu-Yamakawa (FOCS 2021). This brings us to our final contribution:
(3) We introduce coherent-runtime expected quantum polynomial time, a
computational model that (a) captures all of our zero-knowledge simulators, (b)
cannot break any polynomial hardness assumptions, and (c) is not subject to the
CCLY impossibility. In light of our positive results and the CCLY negative
results, we propose coherent-runtime simulation to be the right quantum
analogue of classical expected polynomial-time simulation.
- Abstract（参考訳）: 量子巻き戻しの大きな困難は、測定が破壊的であり、量子状態から情報を抽出することで、それを不可逆的に変化させるという事実である。
これは、敵の状態を保存することが不可欠であるゼロ知識シミュレーションの文脈で特に問題となる。
本研究では,抽出とゼロ知識シミュレーションの文脈で量子巻き戻しを行う新しい手法を開発し,(1)内部状態を乱さずに量子巻き戻しによって量子逆転から情報を抽出する方法を示す。
この手法を用いて、グラフ非同型のgoldreich-micali-wigdersonプロトコルやnpのfeige-shamirプロトコルといった重要な対話プロトコルが量子敵に対するゼロ知識であることが証明される。
2) NPのGoldreich-Kahanプロトコルは、古典的シミュレータの自然な量子拡張と見なせるシミュレータを用いて、量子後ゼロの知識であることを示す。
本研究は,チア・チュン・リュー・ヤマカワ (FOCS 2021) による近年の不可解な結果と矛盾しているように見えるブラックボックスゼロ知識を無視可能なシミュレーション誤差で実現した。
3)コヒーレント実行時の期待量子多項式時間(coherent-runtime expected quantum polynomial time)を導入します。
(a)ゼロ知識シミュレータのすべてをキャプチャします。
(b)多項式硬度仮定を破ることはできず、
(c)cclyの不可能性に従わない。
正の結果とccly負の結果に照らして,古典的多項式時間シミュレーションの正しい量子アナログとなるコヒーレント・ランタイムシミュレーションを提案する。
関連論文リスト
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
d可変RZゲートとG-dクリフォードゲートを含む量子回路を与えられた場合、学習者は純粋に古典的な推論を行い、その線形特性を効率的に予測できるだろうか?
我々は、d で線形にスケーリングするサンプルの複雑さが、小さな予測誤差を達成するのに十分であり、対応する計算の複雑さは d で指数関数的にスケールすることを証明する。
我々は,予測誤差と計算複雑性をトレードオフできるカーネルベースの学習モデルを考案し,多くの実践的な環境で指数関数からスケーリングへ移行した。
論文 参考訳（メタデータ） (2024-08-22T08:21:28Z) - Quantum Simulations for Strong-Field QED [0.0]
強磁場QED(SFQED)の3+1$次元での量子シミュレーションを行う。
ブライト・ウィーラー対生成に関連する相互作用は量子回路に変換される。
ヌルダブルスリット」実験の量子シミュレーションは古典シミュレーションとよく一致している。
論文 参考訳（メタデータ） (2023-11-30T03:05:26Z) - Quantum data learning for quantum simulations in high-energy physics [55.41644538483948]
本研究では,高エネルギー物理における量子データ学習の実践的問題への適用性について検討する。
我々は、量子畳み込みニューラルネットワークに基づくアンサッツを用いて、基底状態の量子位相を認識できることを数値的に示す。
これらのベンチマークで示された非自明な学習特性の観察は、高エネルギー物理学における量子データ学習アーキテクチャのさらなる探求の動機となる。
論文 参考訳（メタデータ） (2023-06-29T18:00:01Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。
我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。
すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
論文 参考訳（メタデータ） (2023-03-02T14:18:17Z) - Quantum simulation of quantum mechanical system with spatial
noncommutativity [0.0]
空間的非可換性を持つ量子力学系の量子シミュレーションを実証する。
我々は、そのような非可換量子系のハミルトニアンを通常の量子力学ハミルトニアンにマッピングするために、新しい群理論形式を用いる。
論文 参考訳（メタデータ） (2022-11-15T17:51:16Z) - Post-Quantum Zero-Knowledge with Space-Bounded Simulation [8.69082943773532]
近距離量子デバイスとより互換性のある,量子後ゼロ知識の詳細な概念を導入する。
対数量子空間 $s$ と古典空間を持つ検証器に対しては、$f(s)=2s$ に対して$(s,f)$-空間有界 QZK が得られることを示す。
超対数量子空間$s$の検証器について、量子後一方向の存在を仮定すると、完全に黒の$(s,f)$空間有界QZKプロトコルが示される。
論文 参考訳（メタデータ） (2022-10-12T11:13:56Z) - Probing finite-temperature observables in quantum simulators of spin
systems with short-time dynamics [62.997667081978825]
ジャジンスキー等式から動機付けられたアルゴリズムを用いて, 有限温度可観測体がどのように得られるかを示す。
長範囲の逆場イジングモデルにおける有限温度相転移は、捕捉されたイオン量子シミュレータで特徴づけられることを示す。
論文 参考訳（メタデータ） (2022-06-03T18:00:02Z) - Error mitigation and quantum-assisted simulation in the error corrected
regime [77.34726150561087]
量子コンピューティングの標準的なアプローチは、古典的にシミュレート可能なフォールトトレラントな演算セットを促進するという考え方に基づいている。
量子回路の古典的準確率シミュレーションをどのように促進するかを示す。
論文 参考訳（メタデータ） (2021-03-12T20:58:41Z) - On the Concurrent Composition of Quantum Zero-Knowledge [11.09538194395154]
コンカレントコンポジションにおける量子時間検証器(量子ゼロ知識)に対するゼロ知識セキュアの概念について検討する。
この結果から,QMAの量子知識系が従来よりも優れたパラメータを持つことを示す。
論文 参考訳（メタデータ） (2020-12-05T23:09:29Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。