古典的な線形代数ソルバーは、同様の速度で量子アルゴリズムを実装できますか？
量子アルゴリズムは、初期状態の量子ビットのレジスタから始まり、ユニタリ演算子（アルゴリズム）がそれらの量子ビットの状態を操作し、次に量子ビットの状態が読み取られます（または単一の状態に関する少なくともいくつかの情報）アルゴリズムの実行）。
量子コンピューターは、量子状態に対する単一作用の問題に答えているように私には思えます。これは「ちょうど」線形代数の問題です。ですから、量子コンピューターは線形代数計算機と見なすことができると思います。
では、なぜ量子力学が必要なのでしょうか。線形代数演算を実装する古典的なシステムを見つけて、これを使用して量子コンピューター用に設計されたアルゴリズムを実装することはできませんか？もちろん、古典的なデジタルコンピュータでは不十分です。これらのマシンは、高次元空間でのベクトルの操作ではなく、情報のバイナリ処理に基づいています。
質問：デジタル古典的コンピューターと同様の高速化を享受しながら、「量子コンピューター」アルゴリズムを実装できる古典的線形代数ソルバー（古典的アナログコンピューター）の候補はありますか？
質問2：おそらく私は、量子コンピューターを単なる線形代数ソルバーに縮小することによって単純化しすぎています。これは本当ですか？私はどのような複雑さを理解していますか？
回答
あなたが見落としている複雑さは、一般的な場合、あなたが保存する必要があるということです $2^n$ を表す複雑な振幅 $n$古典的にキュービットシステム。したがって、たとえば1000キュービットの量子コンピューターの場合、保存する必要があります$2^{1000}$複雑な振幅。これを行うために振幅ごとに1つの原子を使用したとしても、観測可能な宇宙では原子が不足しています。
私の知る限り、上記は一般的な議論です。ただし、アルゴリズムの表現の必要性を節約するためにいくつかの巧妙な洞察を利用することにより、古典的に扱いやすい方法で特定の量子アルゴリズムを表現する方法がまだあるかもしれません。$2^n$要件。ただし、これは問題固有である可能性が高く、一般的なケースでは機能しない可能性があります。
デジタル計算とアナログ計算に関する質問の声明によると、このサイトには同様の提案について問い合わせた他のスレッドがあります。たとえば、ここ、およびここを参照してください。とりわけ、古典的なアナログシステムはエンタングルメントに関与できません。したがって、量子コンピューターをアナログコンピューターとして再キャストしても、同じように速度が向上することはありません。
それにもかかわらず、@ Attila Kunの回答に加えて、線形代数/機械学習には、高速量子アルゴリズムがありましたが、同様の高速化を備えた古典的なアルゴリズムとして書き直された特定の問題があります。
たとえば、Netflix / Amazon / etcで使用される推奨問題。量子コンピューター上で高速アルゴリズムを持っています。このアルゴリズムは、（当時）最もよく知られている古典的なアルゴリズムよりも指数関数的に改善されました。
しかし、量子アルゴリズムが本当に優れていることを証明しようとして、E。Tangは、実際に「線形代数演算を実装し、これを使用して量子コンピューター用に設計されたアルゴリズムを実装する古典的なシステム」があることを示しました。
Tangの仕事は、非量子化のプログラム、つまり線形代数/機械学習の高速量子アルゴリズムを高速の古典的アルゴリズムとして再設計するプログラムを開始しました。Quanta Magazineの記事では、問題とTangのアプローチについて説明しています。
このスレッドで説明されているように、この非量子化の影響を受けやすい問題は、活発な研究分野です。これは、考慮される行列のランクに依存する場合があります。