論文の概要: A one-query lower bound for unitary synthesis and breaking quantum
cryptography
- arxiv url: http://arxiv.org/abs/2310.08870v1
- Date: Fri, 13 Oct 2023 05:39:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-16 14:26:27.664081
- Title: A one-query lower bound for unitary synthesis and breaking quantum
cryptography
- Title（参考訳）: ユニタリ合成と破壊量子暗号のための一問下限
- Authors: Alex Lombardi, Fermi Ma, John Wright
- Abstract要約: ユニタリ合成問題では、任意の$n$qubitのユニタリ$U$を、任意のブール関数$f$を計算するオラクルで拡張された効率的な量子$A$で実装できるかどうかを問う。
本研究は, 対向する$Af$の最大成功確率を解析することにより, 下位境界の証明を可能にする, 効率的なチャレンジャーアドゲームとしてのユニタリ合成を証明する。
- 参考スコア（独自算出の注目度）: 7.705803563459633
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any
$n$-qubit unitary $U$ can be implemented by an efficient quantum algorithm $A$
augmented with an oracle that computes an arbitrary Boolean function $f$. In
other words, can the task of implementing any unitary be efficiently reduced to
the task of implementing any Boolean function?
In this work, we prove a one-query lower bound for unitary synthesis. We show
that there exist unitaries $U$ such that no quantum polynomial-time oracle
algorithm $A^f$ can implement $U$, even approximately, if it only makes one
(quantum) query to $f$. Our approach also has implications for quantum
cryptography: we prove (relative to a random oracle) the existence of quantum
cryptographic primitives that remain secure against all one-query adversaries
$A^{f}$. Since such one-query algorithms can decide any language, solve any
classical search problem, and even prepare any quantum state, our result
suggests that implementing random unitaries and breaking quantum cryptography
may be harder than all of these tasks.
To prove this result, we formulate unitary synthesis as an efficient
challenger-adversary game, which enables proving lower bounds by analyzing the
maximum success probability of an adversary $A^f$. Our main technical insight
is to identify a natural spectral relaxation of the one-query optimization
problem, which we bound using tools from random matrix theory.
We view our framework as a potential avenue to rule out polynomial-query
unitary synthesis, and we state conjectures in this direction.
- Abstract（参考訳）: ユニタリ合成問題(aaronson-kuperberg 2007)は、任意のブール関数$f$を計算したオラクルで拡張された効率的な量子アルゴリズム$a$によって実装できるかどうかを問うものである。
言い換えれば、任意のユニタリを実装するタスクは、Boolean関数を実装するタスクに効率的に還元できるのだろうか?
本研究では,単項合成における一列下界を証明した。
量子多項式時間 oracle のアルゴリズム $a^f$ が $u$ を実装できないようなユニタリが存在しないことを示し、もしそれが 1 つ (量子) クエリを $f$ にするだけなら、概ね $u$ を実装できることを示した。
我々は、量子暗号プリミティブの存在を証明し(ランダムなオラクルに関連して)、全ての1つの暗号相手に対して安全であることを示す。
このような一問アルゴリズムは、任意の言語を決定でき、古典的検索問題を解くことができ、量子状態も準備できるため、ランダムユニタリの実装や量子暗号の解読は、これらのタスクすべてよりも難しい可能性がある。
この結果を証明するために、一元合成を効率的なチャレンジャー・アドバイザリーゲームとして定式化し、敵の$A^f$の最大成功確率を解析して下界の証明を可能にする。
主な技術的洞察は、ランダム行列理論のツールを用いて、一列最適化問題の自然なスペクトル緩和を特定することである。
我々は、我々のフレームワークを多項式列のユニタリ合成を除外する潜在的な方法とみなし、この方向に予想を述べる。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Quantum State Learning Implies Circuit Lower Bounds [2.2667044928324747]
状態トモグラフィー、擬似ランダム性、量子状態、回路下界の接続を確立する。
わずかに自明な量子状態トモグラフィーアルゴリズムでさえも量子状態合成に関する新しい言明に繋がることを示した。
論文 参考訳（メタデータ） (2024-05-16T16:46:27Z) - Generalized Hybrid Search and Applications to Blockchain and Hash
Function Security [50.16790546184646]
まず,ハイブリッド量子古典戦略を用いて,様々な探索問題を解くことの難しさについて検討する。
次に、ハイブリッド量子古典探索アルゴリズムを構築し、その成功確率を解析する。
論文 参考訳（メタデータ） (2023-11-07T04:59:02Z) - Efficient Quantum State Synthesis with One Query [0.0]
本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。
我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
論文 参考訳（メタデータ） (2023-06-02T17:49:35Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
量子順序付き二項決定図($OBDD$)モデルについて検討する。
入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。
read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
論文 参考訳（メタデータ） (2022-04-22T12:37:56Z) - Quantum search-to-decision reductions and the state synthesis problem [0.4248594146171025]
量子アルゴリズムは古典的な決定オラクルにクエリを行い、所望の量子状態を出力することを示す。
また、逆精度まで$mathsfQMA$問題の証人を生成する量子時間アルゴリズムが存在することも示している。
また、より一般的な$textitstate合成問題$を探索し、ターゲット状態の効率的な合成を目標とする。
論文 参考訳（メタデータ） (2021-11-04T16:52:58Z) - Quantum learning algorithms imply circuit lower bounds [7.970954821067043]
量子アルゴリズムの設計と回路下界の一般接続を確立する。
我々の証明は、学習理論、擬似ランダム性、計算複雑性に関するいくつかの研究に基づいている。
論文 参考訳（メタデータ） (2020-12-03T14:03:20Z) - Topological obstructions to quantum computation with unitary oracles [0.0]
いくつかのタスクは量子回路では不可能であるが、古典的なバージョンはクローン化などが容易である。
プロセストモグラフィ、オラクル中立化、$sqrt[dim U]U$、$UT$、$Udagger$アルゴリズムの制限を示す。
その結果、線形光学の利点を強化し、緩和因果性の実験に挑戦し、多くのアウトカム測定で新しいアルゴリズムを動機づけた。
論文 参考訳（メタデータ） (2020-11-19T18:52:38Z) - Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
計算・比較プログラム(Computer-and-compare program)として知られる回避関数のクラスに対する量子コピー保護スキームを導入する。
我々は,量子乱数オラクルモデル(QROM)において,完全悪意のある敵に対する非自明なセキュリティを実現することを証明した。
補完的な結果として、「セキュアソフトウェアリース」という,ソフトウェア保護の概念の弱さが示される。
論文 参考訳（メタデータ） (2020-09-29T08:41:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。