論文の概要: Explicit Separations for One-Query Unitary Synthesis
- arxiv url: http://arxiv.org/abs/2607.26478v1
- Date: Wed, 29 Jul 2026 05:11:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-30 21:06:25.545046
- Title: Explicit Separations for One-Query Unitary Synthesis
- Title（参考訳）: 1クエリ・ユニタリ合成のための明示的分離
- Authors: Fangqi Dong, Alex Lombardi, Fermi Ma,
- Abstract要約: ユニタリ合成問題は、全ての$n$-qubitユニタリU$が効率的な量子回路で計算可能であるかどうかを問うものである。
我々は、ユニタリ合成の変種(および!)の硬さに関するいくつかの結果を証明する。
以前の研究と比較すると、我々のフレームワークは数学的に単純で、証明できるものよりも柔軟であり、より正確には「完全にランダム」でないユニタリの硬さを捉えている。
- 参考スコア（独自算出の注目度）: 3.246030072506843
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every $n$-qubit unitary $U$ is computable by efficient quantum circuits relative to some classical oracle $f = f_U$ depending on $U$. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly$(n)$ parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries $P\lvert x\rangle = \lvert π(x)\rangle$, as well as random alternating-basis phase unitaries $F_2 \cdot H^{\otimes n} \cdot F_1$. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries $\lvert x\rangle\mapsto α_x \lvert x\rangle$, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.
- Abstract（参考訳）: ユニタリ合成問題 (Aaronson-Kuperberg, CCC 2007) は、任意の$n$-量子ユニタリ$U$が、ある古典的なオラクルの$f = f_U$に対する効率的な量子回路によって計算可能であるかどうかを問うものである。
最近、Lombardi-Ma-Wright (STOC 2024) は、1つのクエリ(またはpoly$(n)$並列クエリ)を任意の古典的なオラクルに生成するアルゴリズムによって、ハール・ランドムのユニタリを効率的に合成することはできないことを示した。
本研究では、ユニタリ合成の変種における難易度(および易易度)に関するいくつかの結果を示す。
1) 1-query vs. 2-query Unitary synthesis: ランダムな置換ユニタリ群を合成するための 1-query lower bounds を証明します $P\lvert x\rangle = \lvert π(x)\rangle$, およびランダムな交互基底位相ユニタリ群$F_2 \cdot H^{\otimes n} \cdot F_1$。
これにより、効率的な(2-クエリ)合成アルゴリズムを持つユニタリの「明示的な」族に対して、1-クエリの下位境界が与えられる。
2) 複素位相ユニタリーの上界: 複素位相ユニタリー $\lvert x\rangle\mapsto α_x \lvert x\rangle$ も考慮する。
この場合、上界を証明し、ダイヤモンド距離でこれらのユニタリを一定に近似する1-クエリアルゴリズム(二相オラクル)が存在する。
より低い限界を証明するために,我々は2つの新しい暗号ゲーム,すなわち,オラクル状態検索ゲームとオラクルチョイ状態ゲームを紹介し,解析する。
従来の研究と比べて、我々のフレームワークは数学的に単純で、証明できるものよりも柔軟であり、より正確には「完全にランダム」でないユニタリを合成する難しさを捉えている。
最後に、この探索ゲームを用いて、位相ユニタリに対する量子プログラム(量子アドバイスに対するユニタリの合成)に対する新しいハードネス・オブ・アロキシメーション結果の証明を行い、1-クエリのユニタリ合成と量子プログラムのよりシャープな分離を与える。
関連論文リスト
- Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory [65.64123585249297]
メモリが$m$ の単位球上の$d$ 次元 1$-Lipschitz 凸関数を最小化する。
まず、そのようなアルゴリズムは、$tilde(fracd2sqrtm)$ Oracle queryを作らなければならないことを示す。
決定論的最適化アルゴリズムでは$tilde(mind1.6,fracd8/3m2/3)$クエリが必要である。
論文 参考訳（メタデータ） (2026-07-21T00:40:59Z) - Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - Quantum State Learning Implies Circuit Lower Bounds [1.5420873135976756]
状態トモグラフィー、擬似ランダム性、量子状態、回路下界の接続を確立する。
わずかに自明な量子状態トモグラフィーアルゴリズムでさえも量子状態合成に関する新しい言明に繋がることを示した。
論文 参考訳（メタデータ） (2024-05-16T16:46:27Z) - A one-query lower bound for unitary synthesis and breaking quantum
cryptography [7.705803563459633]
ユニタリ合成問題では、任意の$n$qubitのユニタリ$U$を、任意のブール関数$f$を計算するオラクルで拡張された効率的な量子$A$で実装できるかどうかを問う。
本研究は, 対向する$Af$の最大成功確率を解析することにより, 下位境界の証明を可能にする, 効率的なチャレンジャーアドゲームとしてのユニタリ合成を証明する。
論文 参考訳（メタデータ） (2023-10-13T05:39:42Z) - Information-Computation Tradeoffs for Learning Margin Halfspaces with
Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。
我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文 参考訳（メタデータ） (2023-06-28T16:33:39Z) - Layered State Discovery for Incremental Autonomous Exploration [106.37656068276901]
Layered Autonomous Exploration (LAE) は、$tildemathcalO(LSrightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightar row_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)Srightarrow_LAln12(Srightarrow_LAln12)のサンプル複雑性を達成するAXの新しいアルゴリズムである。
論文 参考訳（メタデータ） (2023-02-07T22:58:12Z) - 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 Algorithm for Lexicographically Minimal String Rotation [5.905222176603487]
語彙的最小弦回転(lexicographically minimal string rotation, LMSR)は、語彙的順序で弦のすべての回転の中で最小の回転を求める問題である。
LMSRのための$O(n3/4)$量子クエリアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-17T03:13:45Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Quantum algorithms for escaping from saddle points [7.191453718557392]
本研究では,サドル点からの脱出を保証できる保証付き量子アルゴリズムについて検討する。
我々の主な貢献は、勾配降下法における古典的摂動を置き換えるという考え方である。
また、Jordanによる量子勾配計算アルゴリズムの使い方を示す。
論文 参考訳（メタデータ） (2020-07-20T16:42:53Z) - Towards Optimal Separations between Quantum and Randomized Query
Complexities [0.30458514384586394]
入力に対して2O(k)$クエリを行うことで量子アルゴリズムを解くことができることを示す。
任意の定数 $varepsilon>0$ に対して、$O(1)$ 対 $N2/3-varepsilon$ 分離を与える。
論文 参考訳（メタデータ） (2019-12-29T01:42:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。