論文の概要: Conjugate queries can help

• arxiv url: http://arxiv.org/abs/2510.07622v1
• Date: Wed, 08 Oct 2025 23:44:30 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-10 17:54:14.775423
• Title: Conjugate queries can help
• Title（参考訳）: 共役クエリは役に立つ
• Authors: Ewin Tang, John Wright, Mark Zhandry,
• Abstract要約: 入力量子オラクル$U$に対して、指数関数的に多くのブラックボックスクエリで解決できない自然な問題を、$U$と$Udagger$に対して与える。 また、$U$と$Udagger$のみを問う敵に対してセキュアな量子コミットメントスキームを実証するが、その敵が$U*$を問うことができれば安全ではない。
• 参考スコア（独自算出の注目度）: 8.81180616144733
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give a natural problem over input quantum oracles $U$ which cannot be solved with exponentially many black-box queries to $U$ and $U^\dagger$, but which can be solved with constant many queries to $U$ and $U^*$, or $U$ and $U^{\mathrm{T}}$. We also demonstrate a quantum commitment scheme that is secure against adversaries that query only $U$ and $U^\dagger$, but is insecure if the adversary can query $U^*$. These results show that conjugate and transpose queries do give more power to quantum algorithms, lending credence to the idea put forth by Zhandry that cryptographic primitives should prove security against these forms of queries. Our key lemma is that any circuit using $q$ forward and inverse queries to a state preparation unitary for a state $\sigma$ can be simulated to $\varepsilon$ error with $n = \mathcal{O}(q^2/\varepsilon)$ copies of $\sigma$. Consequently, for decision tasks, algorithms using (forward and inverse) state preparation queries only ever perform quadratically better than sample access. These results follow from straightforward combinations of existing techniques; our contribution is to state their consequences in their strongest, most counter-intuitive form. In doing so, we identify a motif where generically strengthening a quantum resource can be possible if the output is allowed to be random, bypassing no-go theorems for deterministic algorithms. We call this the acorn trick.
• Abstract（参考訳）: 入力量子オラクル$U$は指数関数的に多くのブラックボックスクエリでは解決できないが、$U$と$U^*$、または$U$と$U^{\mathrm{T}}$に対して一定数のクエリで解決できる。 また、$U$と$U^\dagger$のみを問う敵に対してセキュアな量子コミットメントスキームを実証するが、相手が$U^*$を問うことができれば安全ではない。 これらの結果は、共役クエリと転置クエリが量子アルゴリズムにより多くのパワーを与え、暗号プリミティブがこれらの形式のクエリに対するセキュリティを証明するべきだ、というZhandry氏の考えに信頼を与えていることを示している。 私たちのキーとなる補題は、$q$フォワードと逆クエリを使って状態の準備単位に$\sigma$を使用する任意の回路は、$n = \mathcal{O}(q^2/\varepsilon)$コピーの$\sigma$で$\varepsilon$エラーにシミュレートできるということです。 したがって、決定タスクでは、(前方および逆)状態準備クエリを用いたアルゴリズムは、サンプルアクセスよりも2次的にしか実行できない。 これらの結果は、既存のテクニックの直接的な組み合わせによるものであり、私たちの貢献は、その成果を最も強く、最も直感的でない形で表現することにあります。 そのような場合、決定論的アルゴリズムのノーゴー定理を回避して、出力がランダムであれば、量子資源を一般化的に強化できるモチーフを同定する。 これをトウモロコシのトリックと呼ぶ。

関連論文リスト

• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• 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)
• Efficient Quantum State Synthesis with One Query [0.0]
  本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。 我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
  論文  参考訳（メタデータ） (2023-06-02T17:49:35Z)
• On the average-case complexity of learning output distributions of quantum circuits [33.76498647184212]
  統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。 この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
  論文  参考訳（メタデータ） (2023-05-09T20:53:27Z)
• Tight Bounds for Quantum Phase Estimation and Related Problems [0.90238471756546]
  精度$delta$と誤差確率$epsilon$は$Omegaleft(frac1deltalog1epsilonright)$であることを示す。 また、多くのアドバイス(アドバイス準備ユニタリの応用)を持つことは、コストを大幅に削減することはなく、また、$U$の固有値に関する知識も少なくないことも示している。
  論文  参考訳（メタデータ） (2023-05-08T17:46:01Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• 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)
• 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)
• Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
  Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。 このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
  論文  参考訳（メタデータ） (2020-02-17T10:53:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。