ホームページ テクノロジー周辺機器 AI 量子アルゴリズムが新しい種類の問題を克服します!

量子アルゴリズムが新しい種類の問題を克服します!

Apr 16, 2023 pm 08:04 PM
計算する 量子

1994 年、数学者は、通常の古典的なコンピューターではできないことを量子コンピューターに実行させる方法を発見しました。この研究は、原理的には、量子力学の規則に基づいたマシンが、多数の数値を主因数に効率的に分解できることを示しています。これは、今日のインターネット セキュリティの基礎の大部分を構成する古典的なコンピューターにとっては非常に困難な作業です。

#それに伴い、楽観主義の波が押し寄せてきました。おそらく研究者たちは、多数の異なる問題を解決できる量子アルゴリズムを発明できるだろうと信じています。

#しかし、進歩は停滞しています。カーネギーメロン大学のライアン・オドネル氏は、「ちょっと残念だ。人々は『これは素晴らしい、きっと他にもあらゆる種類の素晴らしいアルゴリズムが開発されるだろう』と言うだろう。そして彼らはそう言うだろう」と語った。科学者らは、NP と呼ばれる標準セット内の単一の狭いクラスの問題でのみ大幅な高速化を発見しました。これは、因数分解などの効率的な検証可能な解決策があることを意味します。

過去 3 年間、このような状況が続いています。そして4月、研究者らは量子コンピューターが古典的なコンピューターよりも速く解決できる全く新しい種類の問題を発明した。これには、乱雑な出力のみに基づいて複雑な数学的プロセスの入力を計算することが含まれます。この問題が単独の問題なのか、それとも他の多くの問題のうちの最初の問題なのかはまだ判明していません。

「興奮の感覚があります。」とマサチューセッツ工科大学のコンピューター科学者、ヴィノッド・ヴァイクンタナサン氏は語ります。

コンピューター科学者は、量子コンピューターを表す数学的モデルを研究することで、量子コンピューターの何が優れているのかを理解しようとします。通常、彼らは、量子コンピューターまたは古典コンピューターと、オラクルと呼ばれる理想的なコンピューターを組み合わせたモデルを想像します。オラクルは、入力を受け取り、所定の出力を出力する単純な数学関数またはコンピューター プログラムのようなものです。

これらはランダムな動作をする可能性があり、入力がランダムな範囲 (たとえば、12 から 67) 内にある場合は「yes」を出力し、それ以外の場合は「no」を出力します。または、周期的である場合もあるため、1 から 10 までの入力は「はい」を返し、11 から 20 までは「いいえ」を返し、21 から 30 までは再び「はい」を返します。

#これらの周期的な予言の 1 つがあるが、その期間はわからないと仮定します。あなたができることは、それに数値を与えて、それが何を出力するかを確認することだけです。これらの制約の下で、コンピューターはどれくらい早くサイクルを見つけることができるでしょうか? 1993 年、当時モントリオール大学にいたダニエル サイモンは、量子アルゴリズムが、どの古典的なアルゴリズムよりも速く、密接に関連した問題に対する答えを計算できることを発見しました。

量子アルゴリズムが新しい種類の問題を克服します!

この結果により、サイモンは量子コンピューターが大きな利点を持つ可能性がある最初の兆候の 1 つを特定することができました。しかし、彼が主要な会議に論文を提出したところ、却下されました。しかし、この論文は、当時ニュージャージー州のベル研究所で働いていた会議プログラム委員会の若手メンバー、ピーター・ショールの興味をそそった。

ショールはさらに、サイモンのアルゴリズムを微調整して、神託があればその期間を計算できることを発見しました。その後、アルゴリズムを再度微調整して、周期的な予言のように動作する方程式、つまり周期的な因数分解を記述する方程式を解くことができることに気づきました。

ショールの結果は歴史的でした。彼が発見した量子アルゴリズムは、膨大な数をその構成素因数に迅速に還元することができますが、これは既知の古典的なアルゴリズムでは不可能なことです。その後数年で、研究者たちは他の効率的な量子アルゴリズムを発見しました。ショールのアルゴリズムなど、それらの中には指数関数的な利点さえも提供するものもありますが、非周期 NP 問題で顕著な量子的利点を証明できた人は誰もいません。

#進歩が見られないことに、テキサス大学オースティン校のスコット・アーロンソンとラトビア大学のアンドリス・アンバイニスという二人のコンピューター科学者が観察するようになりました。量子優位性の証明は常に、周期性などの非ランダム構造による予測に依存しているようです。 2009 年に、彼らは、ランダムまたは非構造化 NP 問題については大幅な高速化はなく、誰も例外を見つけることができないと推測しました。

彼らの推測は、量子コンピューターの機能を制限します。ただし、特定の種類の非構造化 NP 問題 (答えが「はい」または「いいえ」の問題) については、大幅な高速化はないと述べているだけです。この推測は、より具体的で定量的な答えを見つける必要がある問題、いわゆる検索問題には当てはまりません。

これを念頭に置いて、NTT 社会情報学研究所の山川崇研究者と NTT Research およびプリンストン大学の Mark Zhandry 研究者は、Oded Regev が開発したプロジェクトを調査することにしました。 2005 年に提示された特定の検索質問を試してみましょう。

#すべてが同じ方向を向いている一連の風見鶏を想像してください。それぞれを慎重に押して、突風が方向に影響を与えるようにしてください。 Regev は、最終的な方向に基づいて、最初にどこを指していたかを判断したいと考えています。このような問題は、推力と風が元の方向のランダムな誤差源として機能するため、「誤差学習」として知られるようになりました。古典アルゴリズムと量子アルゴリズムはどちらも解決が難しいという証拠があります。

山川とザンドリーが設定を微調整しました。彼らは、より予測しやすくするために、これらのスタートのパワーを修正しました。彼らはまた、ランダムな神託によって風を決定したため、場合によってはさらにランダムになりますが、完全に休止状態になる場合もあります。

#これらの変更により、研究者らは、量子アルゴリズムが初期方向を効果的に見つけることができることを発見しました。彼らはまた、古典的なアルゴリズムは指数関数的に遅くなる必要があることも証明しました。その後、ショールと同様に、彼らは問題の現実的なバージョンを解決するためにアルゴリズムを適応させ、予測を実際の数式に置き換えました。

コンピューター科学者は、この問題を理解して解決しようとまだ努力しています。 Vaikuntanathan 氏は、これをデータ圧縮時に発生する別の状況に例えました。情報が圧縮されると、2 つのビットが誤って同じ場所に押し込まれ、上書きされる可能性があります。このような衝突を事前に予測して回避するという問題には、いくつかの類似点があります。 「これは基本的に次のような問題のクラスです。おそらくこれらの問題は量子的に解決できるでしょう。」

人々はそう願っています。今日の量子コンピューターの誕生したばかりのバージョンでは、新しい問題のような非構造化問題を解決でき、それらをテストする方法が提供されます。構造化されていない問題は、プログラムに必要なリソースが少なくて済み、あるいはすでにランダムであるため、ノイズの影響を受けにくくなる可能性があるという考えでした。しかし今のところ、この新たな問題は、既存の量子コンピューターでは解決するにはまだ高度すぎるようです。 「奇妙な質問ですね。定義することは考えていませんでした」とアーロンソン氏は言いました。「しかし、振り返ってみると、これには非常に優れた機能がいくつかあります。」

この結果は、非構造化 NP 問題における重要な量子的利点の最初の例を提供します。量子の世界の他の多くの問題は、ほぼ解決不可能から解決可能になるのでしょうか?今ではそう考える理由がさらに増えています。 「これは、量子コンピューターがどのような問題を解決するのが得意なのかについての私たちの見方をある程度変えるものです」とオドネル氏は言う。

以上が量子アルゴリズムが新しい種類の問題を克服します!の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

CUDA の汎用行列乗算: 入門から習熟まで! CUDA の汎用行列乗算: 入門から習熟まで! Mar 25, 2024 pm 12:30 PM

General Matrix Multiplication (GEMM) は、多くのアプリケーションやアルゴリズムの重要な部分であり、コンピューター ハードウェアのパフォーマンスを評価するための重要な指標の 1 つでもあります。 GEMM の実装に関する徹底的な調査と最適化は、ハイ パフォーマンス コンピューティングとソフトウェア システムとハードウェア システムの関係をより深く理解するのに役立ちます。コンピューター サイエンスでは、GEMM を効果的に最適化すると、計算速度が向上し、リソースが節約されます。これは、コンピューター システムの全体的なパフォーマンスを向上させるために非常に重要です。 GEMM の動作原理と最適化方法を深く理解することは、最新のコンピューティング ハードウェアの可能性をより有効に活用し、さまざまな複雑なコンピューティング タスクに対してより効率的なソリューションを提供するのに役立ちます。 GEMMのパフォーマンスを最適化することで

Word文書で足し算、引き算、掛け算、割り算を計算する方法 Word文書で足し算、引き算、掛け算、割り算を計算する方法 Mar 19, 2024 pm 08:13 PM

WORD は強力なワード プロセッサです。Word を使用してさまざまなテキストを編集できます。Excel の表では、足し算、引き算、乗算の計算方法をマスターしました。そのため、Word の表で数値の足し算を計算する必要がある場合は、乗数を引くにはどうすればよいですか? 計算には電卓しか使用できませんか?答えはもちろん「いいえ」です。WORD でも実行できます。今日は、Word文書の表で加算、減算、乗算、除算などの基本的な演算を数式を使って計算する方法を説明しますので、一緒に学びましょう。そこで、今日は、WORD 文書で加算、減算、乗算、除算を計算する方法を詳しく説明します。ステップ 1: WORD を開き、ツールバーの [挿入] の下にある [表] をクリックし、ドロップダウン メニューに表を挿入します。

Python の count() 関数を使用してリスト内の要素の数を数える方法 Python の count() 関数を使用してリスト内の要素の数を数える方法 Nov 18, 2023 pm 02:53 PM

Python の count() 関数を使用してリスト内の要素の数を計算する方法には、特定のコード サンプルが必要です。Python は強力で習得しやすいプログラミング言語として、さまざまなデータ構造を処理するための組み込み関数を多数提供しています。その 1 つは count() 関数で、リスト内の要素の数をカウントするために使用できます。この記事では、count()関数の使い方と具体的なコード例を詳しく説明します。 count() 関数は Python の組み込み関数であり、特定の値を計算するために使用されます。

Java で部分文字列の出現数を再帰的にカウントする Java で部分文字列の出現数を再帰的にカウントする Sep 17, 2023 pm 07:49 PM

2 つの文字列 str_1 と str_2 を指定します。目的は、再帰的プロシージャを使用して、文字列 str1 内の部分文字列 str2 の出現数をカウントすることです。再帰関数は、その定義内で自分自身を呼び出す関数です。 str1 が「Iknowthatyouknowthatiknow」、str2 が「know」の場合、出現回数は -3 になります。例を通して理解しましょう。たとえば、入力 str1="TPisTPareTPamTP"、str2="TP"; 出力 Countofoccurrencesofasubstringrecursi

C# で Math.Pow 関数を使用して指定した数値のべき乗を計算する方法 C# で Math.Pow 関数を使用して指定した数値のべき乗を計算する方法 Nov 18, 2023 am 11:32 AM

C# には、多くの数学関数が含まれる Math クラス ライブラリがあります。これらには、累乗を計算する関数 Math.Pow が含まれており、指定された数値の累乗を計算するのに役立ちます。 Math.Pow 関数の使用法は非常に簡単で、基数と指数を指定するだけです。構文は次のとおりです: Math.Pow(base,exponent); ここで、base は基数を表し、exponent は指数を表します。この関数は double 型の結果、つまりべき乗の計算結果を返します。しましょう

行列の右対角要素の合計を計算する Python プログラム 行列の右対角要素の合計を計算する Python プログラム Aug 19, 2023 am 11:29 AM

人気のある汎用プログラミング言語は Python です。デスクトップ アプリケーション、Web 開発、機械学習など、さまざまな業界で使用されています。幸いなことに、Python には初心者に適したシンプルで理解しやすい構文があります。この記事では、Python を使用して行列の右対角の合計を計算します。マトリックスとは何ですか?数学では、数学的オブジェクトまたはそのプロパティを記述するために長方形の配列または行列を使用します。これは、行と列に配置された数値、記号、または式を含む長方形の配列または表です。例: -234512367574 したがって、これは 3 行 4 列の行列であり、3*4 行列として表されます。さて、行列には​​ 2 つの対角線、主対角線と副対角線があります。

行列式を使用して三角形の面積を計算するJavaプログラム 行列式を使用して三角形の面積を計算するJavaプログラム Aug 31, 2023 am 10:17 AM

はじめに 行列式を使用して三角形の面積を計算する Java プログラムは、3 つの頂点の座標を指定して三角形の面積を計算できる簡潔で効率的なプログラムです。このプログラムは、Java で基本的な算術および代数計算を使用する方法と、Scanner クラスを使用してユーザー入力を読み取る方法を示しているため、ジオメトリを学習または操作する人にとって役立ちます。プログラムはユーザーに三角形の 3 点の座標を入力するように要求し、その座標が読み取られて、座標行列の行列式を計算するために使用されます。行列式の絶対値を使用して面積が常に正であることを確認し、式を使用して三角形の面積を計算し、ユーザーに表示します。このプログラムは簡単に変更して、さまざまな形式での入力を受け入れたり、追加の計算を実行したりできるため、幾何学的計算のための多用途ツールになります。決定要因のランク

合計スコアとパーセンテージを計算する Java プログラムの例 合計スコアとパーセンテージを計算する Java プログラムの例 Sep 11, 2023 pm 06:01 PM

Java プログラムを使用して合計スコアとパーセンテージを計算する方法を示します。合計スコアは利用可能なすべてのスコアの合計を指しますが、パーセンテージという用語は、計算されたスコアを合計スコアで割って、結果の数値 100 を掛けたものを指します。 percentage_of_marks=(obtained_marks/total_marks)×100 例 1 これは、合計スコアとパーセンテージを計算する方法を示す Java プログラムです。 //Totalmarks と Percentagecalculated をデモンストレーションする Java プログラムimportjava.io.*;publicclassTotalMarks_

See all articles