| dbo:abstract
|
- En computació quàntica, l'algorisme de Grover és un algorisme quàntic per a la cerca en una seqüència no ordenada de dades amb N components en un temps , i amb una necessitat addicional d'espai d'emmagatzematge d' (vegeu notació O). Va ser inventat per Lov K. Grover en 1996 En una cerca normal d'una dada, si tenim una seqüència desordenada s'ha de realitzar una inspecció lineal, que necessita un temps d', cosa per la qual l'algorisme de Grover és una millora bastant substancial, evitant, a més, la necessitat de l'ordenació prèvia. El guany obtingut és "només" de l'arrel quadrada, cosa que contrasta amb altres millores dels algorismes quàntics que obtenen millores d'ordre exponencial sobre les seves contrapartides clàssiques. Igual que altres algorismes de naturalesa quàntica, l'algorisme de Grover és un algorisme de caràcter probabilístic, per la qual cosa produeix la resposta correcta amb una determinada probabilitat d'error, que no obstant això, pot obtenir-se tan baixa com es desitje per mitjà d'iteracions. (ca)
- Der Grover-Algorithmus ist ein Quantenalgorithmus zur Suche in einer unsortierten Datenbank mit Einträgen in Schritten und mit Speicherbedarf (siehe O-Notation). Er wurde von Lov Grover im Jahre 1996 veröffentlicht und ist der bislang einzige bekannte Algorithmus, für den bewiesen ist, dass Quantenrechner prinzipiell schneller als klassische Computer sind. Auf einem klassischen Computer ist der prinzipiell schnellstmögliche Suchalgorithmus in einer unsortierten Datenbank die lineare Suche, die Rechenschritte erfordert. Der Grover-Algorithmus liefert damit eine quadratische Beschleunigung, was für große beträchtlich ist. Wie die meisten Quantenalgorithmen ist der Grover-Algorithmus ein probabilistischer Algorithmus, d. h., er gibt die korrekte Antwort mit hoher Wahrscheinlichkeit, wobei die Wahrscheinlichkeit einer fehlerhaften Antwort durch wiederholte Ausführung des Algorithmus verkleinert werden kann. (de)
- In quantum computing, Grover's algorithm, also known as the quantum search algorithm, refers to a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just evaluations of the function, where is the size of the function's domain. It was devised by Lov Grover in 1996. The analogous problem in classical computation cannot be solved in fewer than evaluations (because, on average, one has to check half of the domain to get a 50% chance of finding the right input). Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani proved that any quantum solution to the problem needs to evaluate the function times, so Grover's algorithm is asymptotically optimal. Since classical algorithms for NP-complete problems require exponentially many steps, and Grover's algorithm provides at most a quadratic speedup over the classical solution for unstructured search, this suggests that Grover's algorithm by itself will not provide polynomial-time solutions for NP-complete problems (as the square root of an exponential function is an exponential, not polynomial, function). Unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts, Grover's algorithm provides only a quadratic speedup. However, even quadratic speedup is considerable when is large, and Grover's algorithm can be applied to speed up broad classes of algorithms. Grover's algorithm could brute-force a 128-bit symmetric cryptographic key in roughly 264 iterations, or a 256-bit key in roughly 2128 iterations. As a result, it is sometimes suggested that symmetric key lengths be doubled to protect against future quantum attacks. (en)
- En computación cuántica, el algoritmo de Grover es un algoritmo cuántico para la búsqueda en una secuencia no ordenada de datos con N componentes en un tiempo O (N1/2), y con una necesidad adicional de espacio de almacenamiento de O(logN) (véase notación O). Fue inventado por Lov K. Grover en 1996. En una búsqueda normal de un dato, si tenemos una secuencia desordenada se debe realizar una inspección lineal, que necesita un tiempo de O (N), por lo que el algoritmo de Grover es una mejora bastante sustancial, evitando, además, la necesidad de la ordenación previa. La ganancia obtenida es cuadrática, lo que contrasta con otras mejoras de los algoritmos cuánticos que obtienen mejoras de orden exponencial sobre sus contrapartidas clásicas. Al igual que otros algoritmos de naturaleza cuántica, el algoritmo de Grover es un algoritmo de carácter probabilístico, por lo que produce la respuesta correcta con una determinada probabilidad de error, que, no obstante, puede obtenerse tan baja como se desee por medio de iteraciones. (es)
- En informatique quantique, l’algorithme de Grover est un algorithme de recherche, permettant de rechercher un ou plusieurs éléments qui répondent à un critère donné parmi éléments non classés en temps proportionnel à et avec un espace de stockage proportionnel à . Il a été découvert par Lov Grover en 1996. Dans les mêmes conditions (recherche parmi des éléments non classés), un algorithme classique ne peut faire mieux qu'une recherche dans un temps proportionnel à , en testant successivement le critère sur chaque élément. L'étendue de la gamme de critères pouvant être utilisée par cet algorithme lui donne un caractère universel, ce qui en fait un des algorithmes les plus importants et potentiellement le plus utile de l'informatique quantique. L'exemple classique d'utilisation de cet algorithme est la recherche, dans un annuaire téléphonique ordinaire classé alphabétiquement, du nom qui correspond à un numéro de téléphone donné. L'algorithme de Grover fonctionne toujours en lui présentant les nombres entiers de 1 à N, représentant dans le cas de l'annuaire une position dans ce dernier. Le critère de sélection est dans ce cas : la position correspond à un numéro de téléphone donné. La position étant connue, on en déduit le nom ou toute autre information liée à la position. Plus généralement, l'ensemble des nombres entiers de 1 à N peut indexer un ensemble de solutions possibles à un problème. Dans ce cas, s'il est possible de vérifier rapidement qu'une solution résout un problème (ce qui est généralement le cas, et ce qui définit même toute une classe importante de problèmes dits de complexité NP), alors il est possible à l'aide de cet algorithme d'accélérer notablement la recherche des solutions de ces problèmes par rapport à une « recherche brute ». Parmi les problèmes NP (et même NP-Complet) qui pourraient être résolus par cet algorithme se trouvent notamment :
* le problème SAT ;
* la coloration de graphe ;
* la détermination d'un chemin hamiltonien dans un graphe ;
* des puzzles, cryptographiques comme « SEND+MORE=MONEY », ou numériques comme le sudoku. Malgré tout, ce genre de problème est souvent de complexité exponentielle par rapport au nombre d'éléments du problème (typiquement, si n est le nombre d'éléments mis en jeu dans le problème). Même si cet algorithme apporte une optimisation non négligeable (quadratique) par rapport à une recherche brute, il transforme un problème de complexité en , qui demeure exponentielle. Certains algorithmes classiques, adaptés à un problème particulier, peuvent faire mieux, surtout si on tolère une solution approximative, ou probabiliste. Mais cet algorithme présente le double avantage d'être généraliste (dès que l'on a l'algorithme pour vérifier une solution, on a automatiquement l'algorithme pour trouver la solution), et de garantir de trouver la ou les solution(s) optimale(s). Il a été prouvé en 1999, par , que l'algorithme de Grover est l'algorithme quantique le plus efficace pouvant traiter le problème de la recherche non structurée. Il est impossible de faire mieux qu'une amélioration quadratique de la complexité, en utilisant le parallélisme du calcul quantique. (fr)
- L'algoritmo di ricerca di Grover è un algoritmo ideato da Lov Grover nel 1996 ai Bell Labs per risolvere un problema di ricerca in un database indifferenziato di N elementi in O(N1/2) tempo usando O(log N) come spazio di memorizzazione.Un classico esempio può essere la ricerca in un elenco telefonico di un nome disponendo solo del numero telefonico. Disponendo di un computer classico si può pervenire al nome dopo aver cercato mediamente metà dell'elenco. L'algoritmo di Grover, sfruttando la proprietà di sovrapposizione dei qubit, può pervenire alla risposta corretta molto più velocemente.L'algoritmo di Grover può essere utilizzato nella Teoria delle collisioni. (it)
- グローバーのアルゴリズムとは、N個の要素をもつ未整序データベースの中から指定された値を検索する探索問題を解くための量子コンピュータのアルゴリズムであり、O(N1/2)のオーダーの計算量と、O(logN)のオーダー（ランダウの記号も参照）のを消費する。1996年にによって開発された。 (ja)
- Algorytm Grovera – algorytm kwantowy przeznaczony do działania na komputerze kwantowym, przedstawiony przez Lova K. Grovera w 1996 i opublikowany w 2001. Algorytm dotyczy przeszukiwania bazy danych składającej się z N elementów w celu znalezienia w niej elementu wyróżnionego. Jest to problem podobny do „odwrotnego” przeszukiwania książki telefonicznej. W książce zawierającej N danych chcemy znaleźć nazwisko posiadacza danego numeru. (pl)
- Алгоритм Гровера (также GSA от англ. Grover search algorithm) — квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения где есть булева функция от n переменных. Был предложен американским математиком Ловом Гровером в 1996 году. Предполагается, что функция задана в виде чёрного ящика, или оракула, то есть в ходе решения можно задавать оракулу только вопрос типа: «чему равна на данном ?», и использовать ответ в дальнейших вычислениях. То есть, задача решения уравнения (1) является общей формой задачи перебора: здесь требуется отыскать «пароль к устройству », что классически требует полного перебора всех вариантов. Алгоритм Гровера находит какой-нибудь корень уравнения, используя обращений к функции , с использованием кубитов. Смысл алгоритма Гровера состоит в «» целевого состояния за счёт убывания амплитуды всех других состояний. Геометрически алгоритм Гровера заключается во вращении текущего вектора состояния квантового компьютера по направлению точно к целевому состоянию (движение по наикратчайшему пути обеспечивает оптимальность алгоритма Гровера). Каждый шаг дает вращение на угол , где угол между и составляет .Дальнейшее продолжение итераций оператора G даст продолжение обхода окружности в вещественной плоскости, порождённой данными векторами. Гроверовское «усиление амплитуды» является, по-видимому, фундаментальным физическим феноменом в квантовой теории многих тел. Например, его учёт необходим для оценки вероятностей событий, которые кажутся «редкими». Процесс, реализующий схему алгоритма Гровера, приводит к взрывному росту первоначально пренебрежимо малой амплитуды, что способно быстро довести её до реально наблюдаемых величин. Алгоритм Гровера также может быть использован для нахождения медианы и среднего арифметического числового ряда. Кроме того, он может применяться для решения NP-полных задач путём исчерпывающего поиска среди множества возможных решений. Это может повлечь значительный прирост скорости по сравнению с классическими алгоритмами, хотя и не предоставляя «полиномиального решения» в общем виде. (ru)
- Em computação quântica, O algoritmo de Grover ou Algoritmo de Busca O(n½) é um algoritmo quântico que encontra com alta probabilidade a entrada exclusiva para uma função de caixa preta que produz um valor de saída específico, usando apenas avaliações da função , em que N é o tamanho do domínio da função. O algoritmo quântico Grover permite uma aceleração enorme em algoritmos de busca que afeta a segurança de muitos criptosistemas, incluindo AES. O algoritmo foi inventado por Lov Grover em 1996. O problema análogo na computação clássica não pode ser resolvido em menos de avaliações (porque, no pior dos casos, o -th membro do domínio pode ser o membro correto). Aproximadamente na mesma época em que Grover publicou seu algoritmo, Bennett, Bernstein, Brassard e Vazirani provaram que qualquer solução quântica para o problema precisa avaliar a função vezes, o algoritmo de Grover é . Foi demonstrado que um computador quântico de variável oculta não local poderia implementar uma pesquisa sobre um banco de dados com items no máximo passos. Isso é mais rápido que a ordem de passos dados pelo algoritmo de Grover. Porém nenhum dos métodos de busca permitirá que computadores quânticos resolvam problemas NP-Completos em tempo polinomial. (pt)
- 格罗弗算法（英語：Grover's algorithm）是一種量子算法，於1996年由電腦科學家洛夫·格罗弗提出。假設現在有一個未知的函數，格罗弗算法只需測試此未知的函數次，其中為此未知函數的定义域的大小，即可以很高的概率找到一特定的輸入值，此輸入值能使此未知函數輸出特定的值。 同樣的問題在經典運算下，需要至少做 次測試（因為在最壞的情況下，可能第個定義域裡的值才是正確答案）。在格罗弗發表他的算法前後，Bennett, Bernstein, Brassard, 和 Vazirani 在相近的時間證明了，任何量子算法解決此問題都最少需要對此未知的函數做 次測試，因此格罗弗算法是渐进最优的。 非局域隱變量量子計算機已經被證明可以在最多 步內實現在N個條目的數據庫裡的搜索，這比格罗弗算法的 還快，然而這些搜索算法並不能使量子計算機在多項式時間內解決NP-Complete 問題。 不像其他的量子算法可能會比相應的經典算法有指數級的加快，格罗弗算法二次方的加快，不過當很大時二次方的加快也相當可觀。格罗弗算法可以在大約 264次迭代內窮舉破解一個128比特的對稱密鑰，在大約 2128次迭代內窮舉破解一個256比特的密鑰。因此，有人提倡對稱密鑰的長度應該加倍以因應未來的量子攻擊。 像其他的量子算法一樣，格罗弗算法是概率性的，意味著這個算法以小於1的概率給出正確答案。雖然實際上對於需要多少次重複才能給出正確的答案並沒有一個上界，但是期望的重複次數並不隨成長。在格罗弗發表此算法的原始論文中稱此算法為數據庫搜索算法，此說法至今仍普遍。此處數據庫相當於是一張存有未知函數的所有輸出值的表，以對應的輸入值為索引。 (zh)
- Алгоритм Ґровера (також GSA від англ. Grover search algorithm) — квантовий алгоритм вирішення задачі перебору, тобто пошуку рішення рівняння де є булева функція від змінних, а — двійковий вектор довжини . Був запропонований американським математиком в 1996 році. Передбачається, що функція задана у вигляді чорного ящика, або оракула, тобто в ході рішення ми можемо тільки задавати оракула питання типу: «чому дорівнює при даному », І після отримання відповіді використовувати його в подальших обчисленнях. Тобто завдання вирішення рівняння (1) є загальною формою завдання перебору; тут потрібно знайти «пароль до пристрою », Що класично вимагає прямого перебору всіх варіантів. Алгоритм Ґровера знаходить деякий корінь рівняння, використовуючи звернень до функції , з використанням кубітів. Сенс алгоритму Ґровера складається в «посиленні амплітуди» цільового стану за рахунок зменшення амплітуди всіх інших станів. Геометрично алгоритм Ґровера полягає в обертанні поточного вектора стану квантового комп'ютера у напрямку точно до цільового стану (рух по найкоротшому шляху забезпечує оптимальність алгоритму Ґровера). Кожен крок дає обертання на кут , де кут між і становить . Подальше продовження ітерацій оператора G дасть продовження обходу кола в речовій площині, породженої даними векторами. Ґроверівське «посилення амплітуди» є, мабуть, фундаментальним фізичним феноменом в квантової теорії багатьох тіл. Наприклад, його облік необхідний для оцінки ймовірностей подій, які здаються «рідкісними». Процес, який реалізує схему алгоритму Ґровера, призводить до вибухового зростання спочатку знехтуваної малої амплітуди, що здатне швидко довести її до реально спостережуваних величин. (uk)
|
| rdfs:comment
|
- L'algoritmo di ricerca di Grover è un algoritmo ideato da Lov Grover nel 1996 ai Bell Labs per risolvere un problema di ricerca in un database indifferenziato di N elementi in O(N1/2) tempo usando O(log N) come spazio di memorizzazione.Un classico esempio può essere la ricerca in un elenco telefonico di un nome disponendo solo del numero telefonico. Disponendo di un computer classico si può pervenire al nome dopo aver cercato mediamente metà dell'elenco. L'algoritmo di Grover, sfruttando la proprietà di sovrapposizione dei qubit, può pervenire alla risposta corretta molto più velocemente.L'algoritmo di Grover può essere utilizzato nella Teoria delle collisioni. (it)
- グローバーのアルゴリズムとは、N個の要素をもつ未整序データベースの中から指定された値を検索する探索問題を解くための量子コンピュータのアルゴリズムであり、O(N1/2)のオーダーの計算量と、O(logN)のオーダー（ランダウの記号も参照）のを消費する。1996年にによって開発された。 (ja)
- Algorytm Grovera – algorytm kwantowy przeznaczony do działania na komputerze kwantowym, przedstawiony przez Lova K. Grovera w 1996 i opublikowany w 2001. Algorytm dotyczy przeszukiwania bazy danych składającej się z N elementów w celu znalezienia w niej elementu wyróżnionego. Jest to problem podobny do „odwrotnego” przeszukiwania książki telefonicznej. W książce zawierającej N danych chcemy znaleźć nazwisko posiadacza danego numeru. (pl)
- En computació quàntica, l'algorisme de Grover és un algorisme quàntic per a la cerca en una seqüència no ordenada de dades amb N components en un temps , i amb una necessitat addicional d'espai d'emmagatzematge d' (vegeu notació O). Va ser inventat per Lov K. Grover en 1996 Igual que altres algorismes de naturalesa quàntica, l'algorisme de Grover és un algorisme de caràcter probabilístic, per la qual cosa produeix la resposta correcta amb una determinada probabilitat d'error, que no obstant això, pot obtenir-se tan baixa com es desitje per mitjà d'iteracions. (ca)
- En computación cuántica, el algoritmo de Grover es un algoritmo cuántico para la búsqueda en una secuencia no ordenada de datos con N componentes en un tiempo O (N1/2), y con una necesidad adicional de espacio de almacenamiento de O(logN) (véase notación O). Fue inventado por Lov K. Grover en 1996. Al igual que otros algoritmos de naturaleza cuántica, el algoritmo de Grover es un algoritmo de carácter probabilístico, por lo que produce la respuesta correcta con una determinada probabilidad de error, que, no obstante, puede obtenerse tan baja como se desee por medio de iteraciones. (es)
- Der Grover-Algorithmus ist ein Quantenalgorithmus zur Suche in einer unsortierten Datenbank mit Einträgen in Schritten und mit Speicherbedarf (siehe O-Notation). Er wurde von Lov Grover im Jahre 1996 veröffentlicht und ist der bislang einzige bekannte Algorithmus, für den bewiesen ist, dass Quantenrechner prinzipiell schneller als klassische Computer sind. (de)
- In quantum computing, Grover's algorithm, also known as the quantum search algorithm, refers to a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just evaluations of the function, where is the size of the function's domain. It was devised by Lov Grover in 1996. (en)
- En informatique quantique, l’algorithme de Grover est un algorithme de recherche, permettant de rechercher un ou plusieurs éléments qui répondent à un critère donné parmi éléments non classés en temps proportionnel à et avec un espace de stockage proportionnel à . Il a été découvert par Lov Grover en 1996. Parmi les problèmes NP (et même NP-Complet) qui pourraient être résolus par cet algorithme se trouvent notamment : (fr)
- Em computação quântica, O algoritmo de Grover ou Algoritmo de Busca O(n½) é um algoritmo quântico que encontra com alta probabilidade a entrada exclusiva para uma função de caixa preta que produz um valor de saída específico, usando apenas avaliações da função , em que N é o tamanho do domínio da função. O algoritmo quântico Grover permite uma aceleração enorme em algoritmos de busca que afeta a segurança de muitos criptosistemas, incluindo AES. O algoritmo foi inventado por Lov Grover em 1996. (pt)
- Алгоритм Гровера (также GSA от англ. Grover search algorithm) — квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения где есть булева функция от n переменных. Был предложен американским математиком Ловом Гровером в 1996 году. Алгоритм Гровера находит какой-нибудь корень уравнения, используя обращений к функции , с использованием кубитов. (ru)
- 格罗弗算法（英語：Grover's algorithm）是一種量子算法，於1996年由電腦科學家洛夫·格罗弗提出。假設現在有一個未知的函數，格罗弗算法只需測試此未知的函數次，其中為此未知函數的定义域的大小，即可以很高的概率找到一特定的輸入值，此輸入值能使此未知函數輸出特定的值。 同樣的問題在經典運算下，需要至少做 次測試（因為在最壞的情況下，可能第個定義域裡的值才是正確答案）。在格罗弗發表他的算法前後，Bennett, Bernstein, Brassard, 和 Vazirani 在相近的時間證明了，任何量子算法解決此問題都最少需要對此未知的函數做 次測試，因此格罗弗算法是渐进最优的。 非局域隱變量量子計算機已經被證明可以在最多 步內實現在N個條目的數據庫裡的搜索，這比格罗弗算法的 還快，然而這些搜索算法並不能使量子計算機在多項式時間內解決NP-Complete 問題。 不像其他的量子算法可能會比相應的經典算法有指數級的加快，格罗弗算法二次方的加快，不過當很大時二次方的加快也相當可觀。格罗弗算法可以在大約 264次迭代內窮舉破解一個128比特的對稱密鑰，在大約 2128次迭代內窮舉破解一個256比特的密鑰。因此，有人提倡對稱密鑰的長度應該加倍以因應未來的量子攻擊。 (zh)
- Алгоритм Ґровера (також GSA від англ. Grover search algorithm) — квантовий алгоритм вирішення задачі перебору, тобто пошуку рішення рівняння де є булева функція від змінних, а — двійковий вектор довжини . Був запропонований американським математиком в 1996 році. Алгоритм Ґровера знаходить деякий корінь рівняння, використовуючи звернень до функції , з використанням кубітів. (uk)
|
