量子計算

量子計算を古典的計算機でシミュレートするとN qubitのときにO(2^N)で計算量が増えちゃう。これをなんとかpolynomialに近似できないかな。
・整理整理。まずは、状況。
1. inputはN qubitのひとつのテンソル積で与えられる(inputの段階ではentangleしてない)とする。
2. M qubitのからむ任意の演算Uをすると、outputは2^M個のテンソル積の和で表される。
・目標。
outputをMの多項式個のテンソル積に近似したい。
・困った。
この演算Uをn回すると(Mの多項式)^n個のテンソル積になっちゃうよね。。。まぁ、Uをn回って演算をVとして、それのoutputを多項式個にすればいいんだけど。でも、そうすると演算ごとに近似を作らなきゃいけない？あー、もう何やってんだかわかんなくなってきた。
・参考
http://www.brl.ntt.co.jp/event/splaza2005/research/pdf/digest_16.pdf