アカウント名:
パスワード:
量子計算機で高速で古典計算機では低速になる問題を見つけたという話だな
違う。「量子計算機で高速で古典計算機では低速になる問題を見つけ」るための方法を、「出力が周期性のような『構造』を持たない関数」に対しても示した、というもの。
そもそも「量子計算機で高速で古典計算機では低速になる問題が存在する」こと(BPP≠BQP)って示せたんだっけ?
P≠PSPACEも示されていないはずなのでBPP≠BQPは示せませんね。(P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE)今回のものも、古典計算機で計算が難しい問題が存在することは認めましょうという仮定(P≠NP)を置いたときにBPP≠BQPが導かれるというものです。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
計算機科学者とは、壊れていないものを修理する人々のことである
新たな解法を見つけたというよりは (スコア:0)
量子計算機で高速で古典計算機では低速になる問題を見つけたという話だな
Re: (スコア:0)
違う。
「量子計算機で高速で古典計算機では低速になる問題を見つけ」るための方法を、
「出力が周期性のような『構造』を持たない関数」に対しても示した、というもの。
Re: (スコア:0)
そもそも「量子計算機で高速で古典計算機では低速になる問題が存在する」こと(BPP≠BQP)って示せたんだっけ?
Re:新たな解法を見つけたというよりは (スコア:0)
P≠PSPACEも示されていないはずなのでBPP≠BQPは示せませんね。(P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE)
今回のものも、古典計算機で計算が難しい問題が存在することは認めましょうという仮定(P≠NP)を置いたときにBPP≠BQPが導かれるというものです。