論文の概要: Complexity and hardness of random peaked circuits
- arxiv url: http://arxiv.org/abs/2510.00132v1
- Date: Tue, 30 Sep 2025 18:10:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-03 14:32:17.167869
- Title: Complexity and hardness of random peaked circuits
- Title（参考訳）: ランダムピーク回路の複雑さと硬さ
- Authors: Yuxuan Zhang,
- Abstract要約: ランダムピーク回路の明示的な構成について検討する。
本手法により生成された回路は非自明であることを示す。
また、検証可能な量子優位プロトコルの実用的な試みとしてピーク回路を用いて検討する。
- 参考スコア（独自算出の注目度）: 6.472219867780061
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Near-term feasibility, classical hardness, and verifiability are the three requirements for demonstrating quantum advantage; most existing quantum advantage proposals achieve at most two. A promising candidate recently proposed is through randomly generated peaked circuits. In this work, we study an explicit construction for random peaked circuits: first selecting a random circuit $C$ of polynomial size, which forms a $k$-design. Subsequently, a second random circuit $C'$ is chosen from the same architecture, subject to a postselection criterion: $C'$ must exhibit a high overlap with $C$ in one of their rows. Utilizing unitary design properties, we demonstrate that the circuits generated by this method are non-trivial; specifically, $C'$ is provably far from $C^\dagger$. Indeed, with overwhelmingly high probability, a random peaked circuit generated this way is non-compressible and is of circuit complexity $\tilde \Omega(nk)$. This resolves an open problem posed by Aaronson in 2022. Secondly, we analytically establish that estimating the peakedness of a random peaked circuit to within a $2^{-\text{poly}(n)}$ additive error, is average-case \#P-hard. When the additive error is relaxed to $1/\text{poly}(n)$, we note that the worst-case scenario for this problem is BQP-complete. Under widely accepted assumptions on random quantum circuits, we identify a regime where no classical polynomial-time sequential simulator attains inverse-polynomial additive accuracy on the peak on a non-negligible fraction of instances. Thirdly, we study using peaked circuits as a practical attempt for a verifiable quantum advantage protocol. While the postselection method for generating peaked circuits could be costly, we demonstrate that numerical search for $C'$ with randomized initialization successfully returns a random peaked circuit, achieving the properties as theoretically predicted.
- Abstract（参考訳）: 量子優位性を示すための3つの要件は、短期実現可能性、古典的硬度、検証性である。
最近提案された有望な候補はランダムに生成されたピーク回路である。
本研究では、まず、ランダム回路を$C$の多項式サイズで選択し、$k$-designを形成するランダム回路の明示的な構成について検討する。
その後、第2のランダム回路である$C'$が同じアーキテクチャから選択され、ポストセレクションの基準に従う:$C'$は行の1つで$C$と高い重複を示す必要がある。
ユニタリ設計特性を利用すると、この手法によって生成される回路は非自明であることが示され、具体的には$C'$は$C^\dagger$からかなり遠い。
実際、圧倒的に高い確率で、この方法で生成されたランダムピーク回路は圧縮不可能であり、回路複雑性$\tilde \Omega(nk)$である。
これにより、2022年にアーロンソンが提起した開問題は解決される。
第二に、ランダムピーク回路のピーク度を2^{-\text{poly}(n)}$加法誤差で推定することが平均ケース \#P-hard であることを解析的に確立する。
加算誤差が1/\text{poly}(n)$に緩和されると、この問題の最悪のシナリオはBQP完全である。
ランダムな量子回路に関する広く受け入れられている仮定の下では、古典多項式時間シーケンシャルシミュレータが、ピークにおける非無視可能なインスタンスの分数での逆多項式加法的精度を達成できない状態を特定する。
第3に、検証可能な量子優位プロトコルの実用的な試みとしてピーク回路を用いて検討する。
ピーク回路生成のためのポストセレクション法はコストがかかる可能性があるが、ランダム化初期化による$C'$の数値探索がランダムにピーク回路を返却し、その特性を理論的に予測できることを示した。
関連論文リスト
- Unconditional Pseudorandomness against Shallow Quantum Circuits [13.400821866479635]
我々は、浅い深度量子回路クラスに対して、無条件で効率的な擬似ランダム構造を初めて確立する。
我々の研究は、制限された敵の自然クラスに対して、量子計算の擬似ランダム性を無条件で達成できることを実証している。
論文 参考訳（メタデータ） (2025-07-24T20:33:26Z) - Entanglement dynamics and Page curves in random permutation circuits [0.0]
計算基底をランダムに透過する量子回路によって生成されるアンサンブルについて検討する。
本研究は,多体システムにおけるエンタングルメント生成における古典的特徴の影響を明らかにするものである。
論文 参考訳（メタデータ） (2025-05-09T16:09:48Z) - On verifiable quantum advantage with peaked circuit sampling [9.551919087634522]
このような回路から1/textpoly(n)$のピーク値を得るには、圧倒的な確率で$tau_p = Omega(tau_r/n)0.19)$が必要である。
また、このモデルでは非自明なピーク性も可能であるという数値的な証拠を与える。
論文 参考訳（メタデータ） (2024-04-22T18:00:06Z) - Simulation of IBM's kicked Ising experiment with Projected Entangled
Pair Operator [71.10376783074766]
我々は最近,誤りを軽減した量子回路を用いてエミュレートされた127量子ビットキックド・イジングモデルの古典的シミュレーションを行った。
提案手法はハイゼンベルク図の射影的絡み合ったペア作用素(PEPO)に基づいている。
我々はクリフォード展開理論を開発し、正確な期待値を計算し、それらをアルゴリズムの評価に利用する。
論文 参考訳（メタデータ） (2023-08-06T10:24:23Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Fast Rates for Maximum Entropy Exploration [52.946307632704645]
エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。
本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。
訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。
軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-03-14T16:51:14Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - Average-case hardness of estimating probabilities of random quantum
circuits with a linear scaling in the error exponent [0.0]
ランダム量子回路の確率を出力するための加算近似計算の難しさを考察する。
m$ゲートを持つハールランダム回路に対しては、平均ケース加法近似の$mathsfcoC_=P$硬さを2-O(m)$の精度で示す。
ランダム$p=1$ QAOA および IQP 回路の場合、平均の場合、出力確率を 2-O(n)$ の加算誤差の範囲内で近似するのは $mathsfcoC_=P$ であることを示す。
論文 参考訳（メタデータ） (2022-06-12T02:35:51Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
本研究では,典型的な回路インスタンスにおける測定結果の分布に要するゲート数について検討する。
我々の反集中の定義は、予測衝突確率が分布が均一である場合よりも大きい定数因子に過ぎないということである。
ゲートが1D環上で最寄りである場合と、ゲートが長距離である場合の両方において、$O(n log(n))ゲートも十分であることを示す。
論文 参考訳（メタデータ） (2020-11-24T18:44:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。