量子計算の複雑さにおける驚くべき新しい証拠は、遊び心のある思考実験で最もよく理解されるかもしれません。 お風呂を走り、浮かぶ棒磁石の束を水に捨てます。 各磁石は、その向きを前後に反転させ、隣接する磁石と整列させようとします。 それは他の磁石を押したり引いたりして、見返りに押したり引いたりします。 今、これに答えてみてください：システムの最終的な配置はどうなりますか？
この問題とそれに似た他の問題は、非常に複雑であることがわかりました。 磁石が数百個を超えると、コンピューターシミュレーションで答えを吐き出すのに途方もない時間がかかります。
次に、これらの磁石を量子化します。個々の原子は、量子世界のビザンチンの法則に従います。 ご想像のとおり、問題はさらに難しくなります。 「相互作用はより複雑になります」と言いました ヘンリーユエン コロンビア大学の。 「XNUMXつの隣接する「量子磁石」がいつ幸せになるかについては、より複雑な制約があります。」
これらの単純に見えるシステムは、古典的なバージョンと量子バージョンの両方で、計算の限界についての並外れた洞察を提供してきました。 古典的または非量子システムの場合、 コンピュータサイエンスの画期的な定理 私たちをさらに連れて行きます。 PCP定理（「確率的にチェック可能な証明」）と呼ばれるこの定理は、磁石の最終状態（またはそれに関連する側面）を計算するのが非常に難しいだけでなく、それに至るまでの多くのステップも難しいと述べています。 状況の複雑さはさらに劇的であり、言い換えれば、最終的な状態は神秘的なゾーンに囲まれています。
まだ証明されていないPCP定理の別のバージョンは、特に量子の場合を扱っています。 コンピューター科学者は、量子PCP予想が真実であると疑っており、それを証明することで、量子問題の複雑さについての私たちの理解が変わるでしょう。 これは、量子計算の複雑さの理論において、間違いなく最も重要な開かれた問題であると考えられています。 しかし、これまでのところ、到達不可能なままです。
XNUMX年前、XNUMX人の研究者が私たちがそこに到達するのを助けるための中間目標を特定しました。 彼らは思いついた より単純な仮説、「低エネルギートリビアル状態なし」（NLTS）予想として知られています。これは、量子PCP予想が真である場合に真でなければなりません。 それを証明することは、必ずしも量子PCP予想を証明することを容易にするわけではありませんが、それはその最も興味深い質問のいくつかを解決するでしょう。
それから先月、XNUMX人のコンピューター科学者 NLTS予想を証明した。 その結果は、コンピュータサイエンスと量子物理学に大きな影響を及ぼします。
「とてもエキサイティングです」と言いました ドリット・アハラノフ エルサレムのヘブライ大学の。 「それは人々が量子PCP予想のより難しい問題を調査することを奨励するでしょう。」
新しい結果を理解するには、原子のセットなどの量子系を描くことから始めます。 各原子には、軸に沿って指すという点で、磁石の配置にいくぶん似ているスピンと呼ばれる特性があります。 しかし、磁石の配列とは異なり、原子のスピンは、異なる方向が同時に混合した状態になる可能性があります。これは、重ね合わせとして知られる現象です。 さらに、離れた領域からの他の原子のスピンを考慮せずに、XNUMXつの原子のスピンを記述することは不可能かもしれません。 これが起こるとき、それらの相互に関連する原子は量子もつれの状態にあると言われます。 絡み合いは注目に値しますが、壊れやすく、熱的相互作用によって簡単に破壊されます。 システム内の熱が多ければ多いほど、システムを絡ませることは難しくなります。
ここで、原子の束が絶対零度に近づくまで冷却することを想像してみてください。 システムが冷たくなり、絡み合いのパターンがより安定するにつれて、そのエネルギーは減少します。 可能な限り低いエネルギー、つまり「地上エネルギー」は、システム全体の複雑な最終状態の簡潔な説明を提供します。 または、少なくとも、計算できればそうなるでしょう。
1990年代後半から、研究者は、特定のシステムでは、この地上エネルギーを妥当な時間枠で計算できないことを発見しました。
ただし、物理学者は、システムがより暖かく、絡み合いが少なく、したがってより単純であるため、地上エネルギーに近い（ただし、完全にそこにあるわけではない）エネルギーレベルを計算する方が簡単であると考えました。
コンピュータ科学者は同意しませんでした。 古典的なPCP定理によれば、最終状態に近いエネルギーは、最終エネルギー自体と同じように計算するのが困難です。 したがって、PCP定理の量子バージョンは、真の場合、地上エネルギーの前駆体エネルギーを地上エネルギーと同じように計算するのが難しいと言うでしょう。 古典的なPCP定理が真であるため、多くの研究者は量子バージョンも真であるべきだと考えています。 「確かに、量子バージョンは真実でなければなりません」とユエンは言いました。
そのような定理の物理的な意味は深いでしょう。 これは、高温でエンタングルメントを保持する量子システムが存在することを意味します。これは、物理学者の期待とは完全に矛盾しています。 しかし、そのようなシステムが存在することを誰も証明できませんでした。
2013年、カリフォルニア州サンタバーバラにあるMicrosoftResearchのステーションQで働いていたMichaelFreedmanとMatthewHastingsが、問題を絞り込みました。 彼らは、コンピューターがそれらをシミュレートするのに必要な回路の量というXNUMXつのメトリックだけでは、最低およびほぼ最低のエネルギーを計算するのが難しいシステムを探すことにしました。 これらの量子システムは、それらを見つけることができれば、それらの最低エネルギーのすべてでエンタングルメントの豊富なパターンを保持する必要があります。 そのようなシステムの存在は、量子PCP予想を証明しません—考慮すべき他の硬度測定基準があるかもしれません—しかし、それは進歩として数えられます。
コンピュータ科学者はそのようなシステムを知りませんでしたが、どこでそれらを探すべきかを知っていました。量子エラー訂正と呼ばれる研究分野では、研究者は原子を妨害から保護するように設計されたエンタングルメントのレシピを作成します。 各レシピはコードと呼ばれ、身長の高いコードと低いコードの両方が多数あります。
2021年の終わりに、コンピューター科学者 大きな進歩を遂げました 本質的に理想的な性質の量子誤り訂正コードを作成する際に。 その後の数か月にわたって、他のいくつかの研究者グループがそれらの結果に基づいてさまざまなバージョンを作成しました。
過去XNUMX年間、関連プロジェクトで協力してきた新しい論文のXNUMX人の著者が集まって、新しいコードのXNUMXつが、フリードマンとヘイスティングスが仮定した種類の量子システムを作成するために必要なすべての特性を備えていることを証明しました。 。 そうすることで、彼らはNLTS予想を証明した。
彼らの結果は、エンタングルメントが必ずしも物理学者が考えていたほど壊れやすく、温度に敏感であるとは限らないことを示しています。 そして、それは量子PCP予想を支持し、地上エネルギーから離れていても、量子システムのエネルギーを計算することは事実上不可能なままである可能性があることを示唆しています。
「それは、真実である可能性が低いと思われたことが真実であることを私たちに教えてくれます」と言った アイザック・キム カリフォルニア大学デービス校の。 「非常に奇妙なシステムではありますが。」
研究者たちは、完全な量子PCP予想を証明するには、さまざまな技術ツールが必要になると考えています。 しかし、彼らは現在の結果が彼らを近づけるだろうと楽観的である理由を見ています。
彼らはおそらく、新しく発見されたNLTS量子システムが（理論的には可能ですが）実際に自然界で作成できるかどうか、そしてそれらがどのように見えるかに最も興味をそそられます。 現在の結果によると、それらは、実験室で生成されたことがなく、天文学的な数の原子を使用してのみ構築できる長距離エンタングルメントの複雑なパターンを必要とします。
「これらは高度に設計されたオブジェクトです」と述べています。 チンメイ・ニルケ、カリフォルニア大学バークレー校のコンピューター科学者であり、新しい論文の共著者である アヌラグ安州 ハーバード大学と ニコラス・ブリュックマン ユニバーシティカレッジロンドンの。
「本当に遠くの量子ビットを結合する能力があれば、システムを実現できると思います」と安州氏は語った。 「しかし、実際に低エネルギースペクトルに到達するために取るべき別の旅があります。」 Breuckmann氏は、次のように付け加えました。「宇宙にはNLTSという部分があるかもしれません。 知らない。"
