An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem, is a quantum algorithm invented by and Umesh Vazirani in 1992. It is a restricted version of the Deutsch–Jozsa algorithm where instead of distinguishing between two different classes of functions, it tries to learn a string encoded in a function. The Bernstein–Vazirani algorithm was designed to prove an between complexity classes BQP and BPP.

Property Value
dbo:abstract
  • The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem, is a quantum algorithm invented by and Umesh Vazirani in 1992. It is a restricted version of the Deutsch–Jozsa algorithm where instead of distinguishing between two different classes of functions, it tries to learn a string encoded in a function. The Bernstein–Vazirani algorithm was designed to prove an between complexity classes BQP and BPP. (en)
  • El Algoritmo de Bernstein–Vazirani es un algoritmo cuántico desarrollado por Ethan Bernstein y Umesh Vazirani en 1992.​ En esencia, permite conocer un string binario, esto es, una cadena de caracteres compuesta de ceros y unos (por ejemplo: s = 0010110101001), que está contenido en una función. Más concretamente, se sabe que dicha función toma la forma , donde es otro string y la multiplicación se entiende como producto binario. Este algoritmo funciona de manera similar al de Deutsch-Jozsa, pero en vez de tratar de distinguir entre clases de funciones, busca el string que caracteriza a la función dada. Supongamos a modo de ejemplo que se participa en un juego consistente en encontrar un número oculto escrito en código binario. Con la versión clásica del algoritmo, la única manera de obtener la solución sería ir haciendo comprobaciones del número oculto bit a bit, lo cual requiere al menos N ejecuciones, siendo N el número de bits de s (esto se denota como O(N) en teoría de la complejidad computacional). En el caso del algoritmo de Bernstein-Vazirani, si se consigue codificar dicho número en el string s, una única ejecución del algoritmo bastaría para encontrar el número completo. La importancia de este algoritmo radica en la superioridad que muestra frente a su equivalente clásico, pudiéndose encontrar el string buscado tras una única ejecución. (es)
  • L'algorithme de Bernstein–Vazirani, qui résout le problème de Bernstein–Vazirani est un inventé par et Umesh Vazirani en 1992. C'est une version restreinte de l'algorithme de Deutsch-Jozsa dans laquelle, au lieu de distinguer deux classes de fonctions, on essaie de retrouver une chaîne secrète encodée dans une fonction. Il a été conçu pour prouver la distinction entre les classes de complexité BQP et BPP. (fr)
  • L'algoritmo di Bernstein–Vazirani, che risolve il problema di Bernstein–Vazirani è un algoritmo quantistico inventato da Ethan Bernstein e Umesh Vazirani nel 1992. Si tratta di un caso particolare dell'algoritmo di Deutsch-Jozsa dove invece di distinguere due diverse classi di funzioni, cerca di conoscere una stringa codificata in una funzione. L'algoritmo di Bernstein–Vazirani fu ideato per dimostrare una separazione degli oracoli tra le classi di complessità BQP e BPP. (it)
  • Алгоритм Бернштейна — Вазирани (англ. Bernstein–Vazirani algorithm) — квантовый алгоритм, решающий задачу нахождения -битного числа (в иностранной литературе также употребляется термин скрытая строка), скрытого в черном ящике. Предложен Итаном Бернштейном и Умешем Вазирани в 1993 году. Данный алгоритм решает поставленную задачу значительно быстрее, чем это возможно в неквантовой постановке. Алгоритм может применяться в базах данных, атаках на блочные шифры, тестах производительности для квантовых компьютеров, был реализован на 5- и 16-кубитных квантовых компьютерах IBM. (ru)
dbo:thumbnail
dbo:wikiPageID
  • 61184298 (xsd:integer)
dbo:wikiPageLength
  • 4902 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1121289156 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • The Bernstein–Vazirani algorithm, which solves the Bernstein–Vazirani problem, is a quantum algorithm invented by and Umesh Vazirani in 1992. It is a restricted version of the Deutsch–Jozsa algorithm where instead of distinguishing between two different classes of functions, it tries to learn a string encoded in a function. The Bernstein–Vazirani algorithm was designed to prove an between complexity classes BQP and BPP. (en)
  • L'algorithme de Bernstein–Vazirani, qui résout le problème de Bernstein–Vazirani est un inventé par et Umesh Vazirani en 1992. C'est une version restreinte de l'algorithme de Deutsch-Jozsa dans laquelle, au lieu de distinguer deux classes de fonctions, on essaie de retrouver une chaîne secrète encodée dans une fonction. Il a été conçu pour prouver la distinction entre les classes de complexité BQP et BPP. (fr)
  • L'algoritmo di Bernstein–Vazirani, che risolve il problema di Bernstein–Vazirani è un algoritmo quantistico inventato da Ethan Bernstein e Umesh Vazirani nel 1992. Si tratta di un caso particolare dell'algoritmo di Deutsch-Jozsa dove invece di distinguere due diverse classi di funzioni, cerca di conoscere una stringa codificata in una funzione. L'algoritmo di Bernstein–Vazirani fu ideato per dimostrare una separazione degli oracoli tra le classi di complessità BQP e BPP. (it)
  • Алгоритм Бернштейна — Вазирани (англ. Bernstein–Vazirani algorithm) — квантовый алгоритм, решающий задачу нахождения -битного числа (в иностранной литературе также употребляется термин скрытая строка), скрытого в черном ящике. Предложен Итаном Бернштейном и Умешем Вазирани в 1993 году. Данный алгоритм решает поставленную задачу значительно быстрее, чем это возможно в неквантовой постановке. Алгоритм может применяться в базах данных, атаках на блочные шифры, тестах производительности для квантовых компьютеров, был реализован на 5- и 16-кубитных квантовых компьютерах IBM. (ru)
  • El Algoritmo de Bernstein–Vazirani es un algoritmo cuántico desarrollado por Ethan Bernstein y Umesh Vazirani en 1992.​ En esencia, permite conocer un string binario, esto es, una cadena de caracteres compuesta de ceros y unos (por ejemplo: s = 0010110101001), que está contenido en una función. Más concretamente, se sabe que dicha función toma la forma , donde es otro string y la multiplicación se entiende como producto binario. Este algoritmo funciona de manera similar al de Deutsch-Jozsa, pero en vez de tratar de distinguir entre clases de funciones, busca el string que caracteriza a la función dada. Supongamos a modo de ejemplo que se participa en un juego consistente en encontrar un número oculto escrito en código binario. Con la versión clásica del algoritmo, la única manera de obte (es)
rdfs:label
  • Bernstein–Vazirani algorithm (en)
  • Algoritmo de Bernstein–Vazirani (es)
  • Algoritmo di Bernstein-Vazirani (it)
  • Algorithme de Bernstein-Vazirani (fr)
  • Алгоритм Бернштейна — Вазирани (ru)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License