少数の非Cliffordゲートで準備された量子状態の効率的な学習

本論文では、Cliffordゲートおよび O ( log n ) 個の非Cliffordゲートによって準備された量子状態を効率的に学習する一対のアルゴリズムを提示する。具体的には、高々 t 個の非Cliffordゲートで準備された n 量子ビット状態 | に対し、本アルゴリズムは p o l y ( n , 2 t , 1 / ) の時間と | のコピーを使用して、トレース距離高々 まで | を学習する。このタスクに対する第1のアルゴリズムはより効率的であるが、| の2つのコピーにわたるエンタングル測定を必要とする。第2のアルゴリズムは、実行時間とサンプル複雑性の多項式係数を犠牲にして、単一コピー測定のみを使用する。本アルゴリズムは、より一般的に、十分大きなスタビライザー次元を持つ任意の状態を学習する。ここで、量子状態は 2 k 個のPauli演算子からなるアーベル群によって安定化される場合、スタビライザー次元 k を持つ。また、スタビライザー次元に対する効率的なプロパティテストアルゴリズムも開発しており、これは独立した関心事となる可能性がある。