論文の概要: Classical Simulability of Quantum Circuits with Shallow Magic Depth
- arxiv url: http://arxiv.org/abs/2409.13809v1
- Date: Fri, 20 Sep 2024 18:00:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-07 05:01:49.701157
- Title: Classical Simulability of Quantum Circuits with Shallow Magic Depth
- Title(参考訳): 浅魔術深度量子回路の古典的シミュラビリティ
- Authors: Yifan Zhang, Yuxuan Zhang,
- Abstract要約: 量子マジック(quantum magic)は、量子計算が古典的なシミュレーションを超えることができるリソースである。
以前の結果は、古典的なシミュラビリティに、$T$ゲートや安定化器ランクの数によって特徴づけられる量子魔法の量と結びついている。
本研究では,Clifford層と$T$層を交互に組み合わせた量子回路の古典的シミュラビリティについて検討する。
- 参考スコア(独自算出の注目度): 12.757419723444956
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum magic is a resource that allows quantum computation to surpass classical simulation. Previous results have linked the amount of quantum magic, characterized by the number of $T$ gates or stabilizer rank, to classical simulability. However, the effect of the distribution of quantum magic on the hardness of simulating a quantum circuit remains open. In this work, we investigate the classical simulability of quantum circuits with alternating Clifford and $T$ layers across three tasks: amplitude estimation, sampling, and evaluating Pauli observables. In the case where all $T$ gates are distributed in a single layer, performing amplitude estimation and sampling to multiplicative error are already classically intractable under reasonable assumptions, but Pauli observables are easy to evaluate. Surprisingly, with the addition of just one $T$ gate layer or merely replacing all $T$ gates with $T^{\frac{1}{2}}$, the Pauli evaluation task reveals a sharp complexity transition from P to GapP-complete. Nevertheless, when the precision requirement is relaxed to 1/poly($n$) additive error, we are able to give a polynomial time classical algorithm to compute amplitudes, Pauli observable, and sampling from $\log(n)$ sized marginal distribution for any magic-depth-one circuit that is decomposable into a product of diagonal gates. Our research provides new techniques to simulate highly magical circuits while shedding light on their complexity and their significant dependence on the magic depth.
- Abstract(参考訳): 量子マジック(quantum magic)は、量子計算が古典的なシミュレーションを超えることができるリソースである。
以前の結果は、古典的なシミュラビリティに、$T$ゲートや安定化器ランクの数によって特徴づけられる量子魔法の量と結びついている。
しかし、量子回路シミュレーションの硬さに対する量子魔法の分布の影響は未解決のままである。
本研究では,3つのタスク,すなわち振幅推定,サンプリング,パウリ可観測値の評価を交互に行う量子回路の古典的シミュラビリティについて検討する。
すべての$T$ゲートが1つの層に分散されている場合、振幅推定と乗法誤差へのサンプリングは、合理的な仮定の下では古典的に難解であるが、パウリ可観測性は容易に評価できる。
驚いたことに、たった1つの$T$ゲート層を追加するか、単にすべての$T$ゲートを$T^{\frac{1}{2}}$に置き換えるだけで、Pauli評価タスクは、PからGapP完全への急激な複雑性遷移を明らかにする。
それでも、精度要件が 1/poly($n$) 加法誤差に緩和されると、振幅を計算するための多項式時間古典的アルゴリズム、Pauli observable を与え、対角ゲートの積に分解可能な任意のマジック-ディープワン回路に対して $\log(n)$ の限界分布からサンプリングすることができる。
我々の研究は、高度に魔法の回路をシミュレートする新しい技術を提供しています。
関連論文リスト
- Pauli path simulations of noisy quantum circuits beyond average case [0.3277163122167433]
深さ$n$ qubitsのランダム量子回路では、パウリパス法を用いて出力状態からのサンプリングを効率よく行うことができる。
我々は、Tゲートであるゲートの分数とノイズ率の相似性について十分な条件を導出し、ノイズがより速い速度で導入された場合、シミュレーションは古典的に容易になることを示す。
論文 参考訳(メタデータ) (2024-07-22T21:58:37Z) - 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) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
我々は、$m=mathcalO(nk)$バイナリ変数を$n$ qubitsだけを使って最適化するために、$k>1$で可変量子ソルバを導入する。
我々は,特定の量子ビット効率の符号化が,バレン高原の超ポリノミウム緩和を内蔵特徴としてもたらすことを解析的に証明した。
論文 参考訳(メタデータ) (2024-01-17T18:59:38Z) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - Simulation of IBM's kicked Ising experiment with Projected Entangled
Pair Operator [71.10376783074766]
我々は最近,誤りを軽減した量子回路を用いてエミュレートされた127量子ビットキックド・イジングモデルの古典的シミュレーションを行った。
提案手法はハイゼンベルク図の射影的絡み合ったペア作用素(PEPO)に基づいている。
我々はクリフォード展開理論を開発し、正確な期待値を計算し、それらをアルゴリズムの評価に利用する。
論文 参考訳(メタデータ) (2023-08-06T10:24:23Z) - Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach [1.806183113759115]
大規模変動量子アルゴリズムは量子優位性を達成するための潜在的な経路として広く認識されている。
本稿では,可観測物のバックプロパゲーションの積分経路に基づく新しい$gammaPPP法を提案する。
我々は,IBMの127量子ビットイーグルプロセッサにおけるゼロノード化実験結果の古典的シミュレーションを行う。
論文 参考訳(メタデータ) (2023-06-09T10:42:07Z) - Exponential quantum speedup in simulating coupled classical oscillators [1.9398245011675082]
本稿では,2n$結合発振器の古典力学に対する量子アルゴリズムを提案する。
我々のアプローチは、調和ポテンシャルに対するシュル「オーディンガー方程式」とニュートン方程式の間の写像を利用する。
提案手法は,古典的コンピュータ上での指数的高速化により,潜在的に実用的な応用を実現できることを示す。
論文 参考訳(メタデータ) (2023-03-23T03:24:03Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳(メタデータ) (2022-07-07T08:04:15Z) - An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian
Simulation [55.41644538483948]
現在の世代のノイズの多い中間スケール量子コンピュータ(NISQ)は、チップサイズとエラー率に大きく制限されている。
我々は、自由フェルミオンとして知られる特定のスピンハミルトニアンをシミュレーションするために、量子回路を効率よく圧縮するために局所化回路変換を導出する。
提案した数値回路圧縮アルゴリズムは、後方安定に動作し、$mathcalO(103)$スピンを超える回路合成を可能にするスピンの数で3次スケールする。
論文 参考訳(メタデータ) (2021-08-06T19:38:03Z) - Learning k-qubit Quantum Operators via Pauli Decomposition [11.498089180181365]
現在の量子系の量子ビット容量の制限により、量子サンプルの複雑さを$k$-qubit量子作用素で調べる。
我々は、$k$-qubitの量子演算の量子サンプルの複雑さが、その量子演算の古典的なサンプルの複雑さに匹敵することを示した。
論文 参考訳(メタデータ) (2021-02-10T01:20:55Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。