@yuichirominato 2019.01.04更新 163views

【ユニバーサル性】Solovay–Kitaev theoremとGottesman–Knill theorem

Gottesman-Knill Solovay-Kitaev クリフォードゲート 量子ゲート

はじめに

単に気になったのでまとめてみます。

Solovay–Kitaev theorem

https://en.wikipedia.org/wiki/Solovay%E2%80%93Kitaev_theorem

In the mathematical theory of computation, the Solovay–Kitaev theorem says, roughly, that if a set of single-qubitquantum gates generates a densesubset of SU(2) then that set is guaranteed to fill SU(2) quickly, which means good approximations to any desired gate can be created using fairly short sequences of gates from the generating set. It is one of the most important fundamental results in the field of quantum computation.[1]Robert M. Solovay and Alexei Kitaev jointly came up with and proved the theorem.

もし単一量子ビットのゲートセットがSU(2)の稠密集合を生成する場合、そのセットはSU(2)を速やかに満たすことが保証される。つまり、そのようなゲートセットでどんなユニタリゲートもいい近似を作り出せる。

稠密集合

数学位相空間論周辺分野において、位相空間X の部分集合A が X において稠密(ちゅうみつ、dense)であるとは、X の各点 x が、A の元であるか、さもなくば A の集積点であるときにいう[。イメージで言えば、X の各点が A の中かさもなくば A の元の「どれほどでも近く」にあるということを表している。例えば、任意の実数は、有理数であるか、さもなくばどれほどでも近い有理数をとることができる

https://ja.wikipedia.org/wiki/%E7%A8%A0%E5%AF%86%E9%9B%86%E5%90%88

SU(2)

n 次の特殊ユニタリ群(とくしゅユニタリぐん、英語: special unitary group)SU(n) とは、行列式が1の n 次ユニタリ行列の為すの事である。群の演算行列の積で与えられる。

下記のSU(2)は2次のSpecial Unitary Groupを略してSU(2)。

https://ja.wikipedia.org/wiki/%E7%89%B9%E6%AE%8A%E3%83%A6%E3%83%8B%E3%82%BF%E3%83%AA%E7%BE%A4

Gottesman–Knill theorem

In quantum computing, the Gottesman–Knill theorem is a theoretical result by Daniel Gottesman and Emanuel Knill that states that stabilizer circuits, circuits that only consist of gates from the normalizer of the qubit Pauli group, also called Clifford group, can be perfectly simulated in polynomial time on a probabilistic classical computer. The Clifford group can be generated solely by using CNOT, Hadamard, and phase gates [1] , therefore stabilizer circuits can be constructed using only these gates.

パウリ演算子もしくはクリフォード群は多項式時間で古典計算機でシミュレートできる。

The reason for the speed up of quantum computers is not yet fully understood. The theorem proves that, for all quantum algorithms with a speed up that relies on entanglement which can be achieved with a CNOT and a Hadamard gate to produce entangled states, this kind of entanglement alone does not give any computing advantage.

CNOTとアダマールゲートから作り出される量子もつれ状態でも、古典計算機より早いとは限らない。

Formal statement

Theorem: A quantum circuit using only the following elements can be simulated efficiently on a classical computer:

下記の条件だけでは古典計算機で効率的にシミュレートできる。

  1. Preparation of qubits in computational basis states,
  2. Quantum gates from the Clifford group (Hadamard gatescontrolled NOT gates, Phase Gate), and
  3. Measurements in the computational basis.

計算基底で量子ビットが準備される。クリフォード群(アダマール、CNOT、フェーズゲート)で構成される。計算基底で量子ビットが測定される。

The Gottesman–Knill theorem shows that even some highly entangled states can be simulated efficiently. Several important types of quantum algorithms use only Clifford gates, most importantly the standard algorithms for entanglement purification and for quantum error correction. From a practical point of view, stabilizer circuits have been simulated in O(n log n) time using the graph state formalism.

結論

Non-CliffordのT-ゲートが大事?

あわせて読みたい

SERVICE

汎用量子コンピュータ向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

汎用量子コンピュータ向け高速シミュレータ

詳しく見る

量子コンピュータ向けクラウドサービス(準備中)

詳しく見る

イジングマシン向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

COMMUNITY

量子コンピュータのことを学びたい、仕事としたいなどの情報交換の場を設け、コミュニティの形成を進めています。オフラインの勉強会と、オンラインのチャットコミュニティの2種類あります。オフラインのConnpassは1400名、オンラインのSlackは880名を超える参加があります。どちらも無料ですのでお気軽にご参加ください。

CONNPASS SLACK

CONTACT

弊社あての連絡はinfo@mdrft.comより用件を明記の上、メールで連絡を頂けますと幸いです。

ブログトップへ Wikiへ移動

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方