論文の概要: On the Computational Hardness of Quantum One-Wayness
- arxiv url: http://arxiv.org/abs/2312.08363v1
- Date: Wed, 13 Dec 2023 18:56:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-12-14 14:24:00.853745
- Title: On the Computational Hardness of Quantum One-Wayness
- Title（参考訳）: 量子ワンウェイネスの計算硬度について
- Authors: Bruno Cavalar, Eli Goldin, Matthew Gray, Peter Hall, Yanyi Liu,
Angelos Pelecanos
- Abstract要約: Pseudorandom状態は、$n$bitsを$log n + 1$ qubitsに圧縮する。
一方向のステートジェネレータは、古典的に$rmPP$oracleにアクセスできる量子アルゴリズムによって破壊することができる。
我々の結果の興味深い意味は、すべての$t(n) = o(n/log n)$に対して、$t(n)$-copy 1-way状態生成器が無条件に存在することである。
- 参考スコア（独自算出の注目度）: 3.5301990305960222
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: There is a large body of work studying what forms of computational hardness
are needed to realize classical cryptography. In particular, one-way functions
and pseudorandom generators can be built from each other, and thus require
equivalent computational assumptions to be realized. Furthermore, the existence
of either of these primitives implies that $\rm{P} \neq \rm{NP}$, which gives a
lower bound on the necessary hardness.
One can also define versions of each of these primitives with quantum output:
respectively one-way state generators and pseudorandom state generators. Unlike
in the classical setting, it is not known whether either primitive can be built
from the other. Although it has been shown that pseudorandom state generators
for certain parameter regimes can be used to build one-way state generators,
the implication has not been previously known in full generality. Furthermore,
to the best of our knowledge, the existence of one-way state generators has no
known implications in complexity theory.
We show that pseudorandom states compressing $n$ bits to $\log n + 1$ qubits
can be used to build one-way state generators and pseudorandom states
compressing $n$ bits to $\omega(\log n)$ qubits are one-way state generators.
This is a nearly optimal result since pseudorandom states with fewer than $c
\log n$-qubit output can be shown to exist unconditionally. We also show that
any one-way state generator can be broken by a quantum algorithm with classical
access to a $\rm{PP}$ oracle.
An interesting implication of our results is that a $t(n)$-copy one-way state
generator exists unconditionally, for every $t(n) = o(n/\log n)$. This
contrasts nicely with the previously known fact that $O(n)$-copy one-way state
generators require computational hardness. We also outline a new route towards
a black-box separation between one-way state generators and quantum bit
commitments.
- Abstract（参考訳）: 古典的暗号を実現するのにどのような計算の困難さが必要かを研究する多くの研究がある。
特に、一方通行関数と擬似乱数発生器は互いに組み合わさり、それを実現するには等価な計算仮定が必要である。
さらに、これらのプリミティブのいずれかの存在は、$\rm{P} \neq \rm{NP}$ であり、必要な硬さの低い境界を与えることを意味する。
また、それぞれのプリミティブのバージョンを量子出力で定義することもできる:それぞれ一方通行状態生成器と擬似ランダム状態生成器である。
古典的な設定とは異なり、どちらのプリミティブも他方から構築できるかどうかは不明である。
擬似乱数状態生成器が一方向状態生成器を構築するのに利用できることが示されているが、その影響は一般には知られていない。
さらに、我々の知る限りでは、一方向状態生成器の存在は複雑性理論において既知の意味を持たない。
我々は、$n$bitsを$\log n + 1$ qubitsに圧縮する擬似ランダム状態が片道状態発生器や擬似ランダム状態の生成に利用でき、$n$bitsを$\omega(\log n)$ qubitsは片道状態発生器であることを示す。
これは、$c \log n$-qubit 出力未満の擬ランダム状態が無条件に存在することを示すため、ほぼ最適な結果である。
また、任意の一方向状態生成器は、$\rm{pp}$ oracle への古典的なアクセスを持つ量子アルゴリズムによって破壊される。
この結果の興味深い意味は、すべての$t(n) = o(n/\log n)$ に対して、$t(n)$-copy one-way state generator が無条件に存在するということである。
これは、$O(n)$-copy 1-way状態生成器が計算の困難さを必要とするという事実とよく対照的である。
また、一方の状態発生器と量子ビットのコミットメントの間のブラックボックス分離に向けた新たな経路を概説する。
関連論文リスト
- Quantum State Learning Implies Circuit Lower Bounds [2.2667044928324747]
状態トモグラフィー、擬似ランダム性、量子状態、回路下界の接続を確立する。
わずかに自明な量子状態トモグラフィーアルゴリズムでさえも量子状態合成に関する新しい言明に繋がることを示した。
論文 参考訳（メタデータ） (2024-05-16T16:46:27Z) - Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。
これまでのところ、不規則な置換は根本的なオープンな問題のままである。
ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
論文 参考訳（メタデータ） (2024-03-07T18:46:58Z) - Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
計算基底の部分集合である$S$に対する部分集合状態は [ frac1sqrt|S|sum_iin S |irangle である。
固定された部分集合サイズ $|S|=s$ に対して、$s = 2n/omega(mathrmpoly(n))$ と $s=omega(mathrmpoly(n))$ が与えられたとき、ランダムな部分集合状態は情報理論上はHaarランダム状態と区別できないことを示す。
論文 参考訳（メタデータ） (2023-12-23T15:52:46Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - Sparse random Hamiltonians are quantumly easy [105.6788971265845]
量子コンピュータの候補は、量子システムの低温特性をシミュレートすることである。
本稿は、ほとんどのランダムハミルトニアンに対して、最大混合状態は十分に良い試行状態であることを示す。
位相推定は、基底エネルギーに近いエネルギーの状態を効率的に生成する。
論文 参考訳（メタデータ） (2023-02-07T10:57:36Z) - Pseudorandom (Function-Like) Quantum State Generators: New Definitions
and Applications [7.2051162210119495]
擬似ランダム状態の新しい定義、新しい性質、応用について検討する。
Pseudorandom quantum state (PRS) は、計算的にハールランドムと区別できない効率的な構成可能な状態である。
対数的な出力長を持つPSSジェネレータは、古典的な通信によるコミットメントと暗号化スキームを暗示している。
論文 参考訳（メタデータ） (2022-11-02T19:24:55Z) - Cryptography from Pseudorandom Quantum States [6.164147034988822]
片道関数は擬似ランダム状態の存在を暗示するが、Kretschmer (TQC'20) は最近、一方通行関数が存在しないが擬似ランダム状態が存在するという相対的なオラクルを構築した。
疑似ランダム状態における興味深い暗号タスクの基盤となる可能性について検討する。
a)の結果として、疑似ランダム状態は不正にセキュアなマルチパーティプロトコルを構築するのに十分である。
論文 参考訳（メタデータ） (2021-12-18T22:53:16Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Improved approximation algorithms for bounded-degree local Hamiltonians [12.961180148172197]
与えられた積状態によって達成される近似比を改善するために使用できる浅量子回路群について述べる。
結果は、$k$-local Hamiltonianと絡み合った初期状態に拡張します。
論文 参考訳（メタデータ） (2021-05-03T22:23:47Z) - Quantum Pseudorandomness and Classical Complexity [0.08158530638728499]
暗号擬似乱数量子状態と擬似乱数ユニタリ変換が存在することを示す。
本稿では、暗号、複雑性理論、量子トモグラフィーにおけるこれらの結果の影響について論じる。
論文 参考訳（メタデータ） (2021-03-16T20:54: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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。