In computational complexity theory and quantum computing, Simon's problem is a computational problem that is proven to be solved exponentially faster on a quantum computer than on a classical (that is, traditional) computer. The quantum algorithm solving Simon's problem, usually called Simon's algorithm, served as the inspiration for Shor's algorithm. Both problems are special cases of the abelian hidden subgroup problem, which is now known to have efficient quantum algorithms.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Problema de Simon (es)
- Problema di Simon (it)
- Algorytm Simona (pl)
- Problema de Simon (pt)
- Simon's problem (en)
|
| rdfs:comment
| - Algorytm Simona – algorytm kwantowy znajdujący rozwiązanie poniższego zagadnienia. (pl)
- Na teoria da complexidade computacional e em Computação quântica, o problema de Simon nos é dado em uma função (implementada por uma caixa preta) de cordas de n bits a cordas de n bits, que é garantida a satisfazer a propriedade de que para alguns que tem para todos , se e somente se ou . Daniel Simon, em 1994, apresentou um algoritmo quântico, normalmente chamado algoritmo de Simon que resolve o problema exponencialmente mais rápido do que qualquer (determinístico ou probabilístico) algoritmo. (pt)
- En álgebra abstracta y computación cuántica, el problema planteado por Daniel R. Simon (conocido como problema de Simon) es un caso particular del problema del subgrupo oculto (Hidden Subgroup Problem, HSP), el cual ha sido útil para el planteamiento de algoritmos cuánticos que son eficientes, a diferencia de sus homólogos clásicos, permitiendo resolver problemas teóricos propuestos en las últimas décadas cuyas soluciones son de vital importancia en el campo de la computación cuántica. (es)
- In computational complexity theory and quantum computing, Simon's problem is a computational problem that is proven to be solved exponentially faster on a quantum computer than on a classical (that is, traditional) computer. The quantum algorithm solving Simon's problem, usually called Simon's algorithm, served as the inspiration for Shor's algorithm. Both problems are special cases of the abelian hidden subgroup problem, which is now known to have efficient quantum algorithms. (en)
- Nella teoria della complessità computazionale e nella computazione quantistica, il problema di Simon è un problema computazionale che può essere risolto in maniera esponenzialmente più veloce su un computer quantistico rispetto a un computer classico (o tradizionale). Il problema di Simon incorpora l'uso di una scatola nera (black box). I problemi con la scatola nera danno agli algoritmi quantistici un vantaggio rispetto agli algoritmi classici. (it)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - En álgebra abstracta y computación cuántica, el problema planteado por Daniel R. Simon (conocido como problema de Simon) es un caso particular del problema del subgrupo oculto (Hidden Subgroup Problem, HSP), el cual ha sido útil para el planteamiento de algoritmos cuánticos que son eficientes, a diferencia de sus homólogos clásicos, permitiendo resolver problemas teóricos propuestos en las últimas décadas cuyas soluciones son de vital importancia en el campo de la computación cuántica. Para resolver el problema de Simon se han desarrollado algoritmos clásicos que utilizan fuerza bruta, de los cuales se sabe que su complejidad es exponencial. Para encontrar una solución eficiente se ha recurrido a algoritmos cuánticos, como el propuesto por el mismo Simon, cuya complejidad es polinomial, reduciendo así el tiempo de cómputo de forma significativa. Se han desarrollado algoritmos cuánticos para otros casos particulares del problema del subgrupo oculto, pero solo son eficientes aquellos que trabajan sobre grupos abelianos (como el de Simon). Para los grupos no abelianos aún no se han encontrado algoritmos cuánticos eficientes, de hecho estos no llegan a tener mejor desempeño que las soluciones clásicas. (es)
- In computational complexity theory and quantum computing, Simon's problem is a computational problem that is proven to be solved exponentially faster on a quantum computer than on a classical (that is, traditional) computer. The quantum algorithm solving Simon's problem, usually called Simon's algorithm, served as the inspiration for Shor's algorithm. Both problems are special cases of the abelian hidden subgroup problem, which is now known to have efficient quantum algorithms. The problem is set in the model of decision tree complexity or query complexity and was conceived by in 1994. Simon exhibited a quantum algorithm that solves Simon's problem exponentially faster and with exponentially fewer queries than the best probabilistic (or deterministic) classical algorithm. In particular, Simon's algorithm uses a linear number of queries and any classical probabilistic algorithm must use an exponential number of queries. This problem yields an between the complexity classes BPP (bounded-error classical query complexity) and BQP (bounded-error quantum query complexity). This is the same separation that the Bernstein–Vazirani algorithm achieves, and different from the separation provided by the Deutsch–Jozsa algorithm, which separates P and EQP. Unlike the Bernstein–Vazirani algorithm, Simon's algorithm's separation is exponential. Because this problem assumes the existence of a highly-structured "black box" oracle to achieve its speedup, this problem has little practical value. However, without such an oracle, exponential speedups cannot easily be proven, since this would prove that P is different from PSPACE. (en)
- Nella teoria della complessità computazionale e nella computazione quantistica, il problema di Simon è un problema computazionale che può essere risolto in maniera esponenzialmente più veloce su un computer quantistico rispetto a un computer classico (o tradizionale). Il problema di Simon incorpora l'uso di una scatola nera (black box). I problemi con la scatola nera danno agli algoritmi quantistici un vantaggio rispetto agli algoritmi classici. Il problema in sé è di poco interesse pratico perché ci sono poche situazioni realistiche in cui ci sia bisogno di risolvere il problema di Simon. Tuttavia, il problema è comunque importante perché si può dimostrare che un algoritmo quantistico può risolvere questo problema in modo esponenzialmente più veloce rispetto a un qualsiasi algoritmo classico conosciuto. Questo è il primo esempio di problema computazionale che può essere risolto in un tempo polinomiale su un computer quantistico. Il problema fu ideato da Daniel Simon nel 1994. Simon mostrò un algoritmo quantistico, spesso detto algoritmo di Simon, che risolve il problema richiedendo esponenzialmente meno tempo computazionale (o più precisamente, chiamate) rispetto al miglior algoritmo classico. Nell'algoritmo di Simon è necessario effettuare un numero lineare di chiamate, mentre l'algoritmo classico ne necessita un numero esponenziale. Questo problema dà una separazione dell'oracolo tra le classi di complessità BPP e BQP, a differenza della separazione data dall'algoritmo di Deutsch-Jozsa, che separa P e EQP. La separazione è esponenziale (relativa a un oracolo) tra la complessità classica e quantistica. L'algoritmo di Simon fu inoltre l'ispirazione per l'algoritmo di Shor. Entrambi i problemi sono casi particolari del problema del sottogruppo nascosto abeliano, per il quale sono conosciuti algoritmi quantistici efficienti. (it)
- Algorytm Simona – algorytm kwantowy znajdujący rozwiązanie poniższego zagadnienia. (pl)
- Na teoria da complexidade computacional e em Computação quântica, o problema de Simon nos é dado em uma função (implementada por uma caixa preta) de cordas de n bits a cordas de n bits, que é garantida a satisfazer a propriedade de que para alguns que tem para todos , se e somente se ou . Daniel Simon, em 1994, apresentou um algoritmo quântico, normalmente chamado algoritmo de Simon que resolve o problema exponencialmente mais rápido do que qualquer (determinístico ou probabilístico) algoritmo. (pt)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
