Analysis
量子物理学：量子因数分解の過剰な単純化
Nature 499, 7457 doi: 10.1038/nature12290
ショアの量子因数分解アルゴリズムは、既知の古典的手法よりも指数関数的に効率が良い。これまでの実験的実行は、その因数を知っていることを前提条件として単純化されていた。しかし、ここで示すように、このアルゴリズムは、全ての合成数に対してコインフリップと等価な回路へ単純化できる。従って、特定の実験の難しさはその単純化のレベルに依存しており、因数分解される数の大きさには依存しない。このアルゴリズムを正当に実行するには、探し求める答えを利用すべきでない。
