PostBQP (original) (raw)
En teoria de la complexitat, la classe de complexitat postBQP és el conjunt de tots els problemes que es poden solucionar amb temps polinòmic per una Màquina de Turing quàntica amb post-selecció amb un error fitat (en el sentit que l'algorisme és correcte almenys 2/3 de les vegades per totes les entrades). La post-selecció no es considera que sigui una característica realista per un ordinador (ni per un de quàntic), però des del punt de vista teòric són unes màquines interessants.
| Property | Value |
|---|---|
| dbo:abstract | En teoria de la complexitat, la classe de complexitat postBQP és el conjunt de tots els problemes que es poden solucionar amb temps polinòmic per una Màquina de Turing quàntica amb post-selecció amb un error fitat (en el sentit que l'algorisme és correcte almenys 2/3 de les vegades per totes les entrades). La post-selecció no es considera que sigui una característica realista per un ordinador (ni per un de quàntic), però des del punt de vista teòric són unes màquines interessants. (ca) In computational complexity theory, PostBQP is a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with postselection and bounded error (in the sense that the algorithm is correct at least 2/3 of the time on all inputs). Postselection is not considered to be a feature that a realistic computer (even a quantum one) would possess, but nevertheless postselecting machines are interesting from a theoretical perspective. Removing either one of the two main features (quantumness, postselection) from PostBQP gives the following two complexity classes, both of which are subsets of PostBQP: * BQP is the same as PostBQP except without postselection * BPPpath is the same as PostBQP except that instead of quantum, the algorithm is a classical randomized algorithm (with postselection) The addition of postselection seems to make quantum Turing machines much more powerful: Scott Aaronson proved PostBQP is equal to PP, a class which is believed to be relatively powerful, whereas BQP is not known even to contain the seemingly smaller class NP. Using similar techniques, Aaronson also proved that small changes to the laws of quantum computing would have significant effects. As specific examples, under either of the two following changes, the "new" version of BQP would equal PP: * if we broadened the definition of 'quantum gate' to include not just unitary operations but linear operations, or * if the probability of measuring a basis state was proportional to instead of for any even integer p > 2. (en) Em teoria da complexidade computacional, PostBQP é uma classe de complexidade que consiste de todos os problemas computacionais solúveis em tempo polinomial em uma Máquina de Turing quântica com e erro limitado (no sentido de que o algoritmo é correto ao menos em 2/3 das vezes para todas as entradas). Pós-seleção não é considerada uma funcionalidade que um computador realístico (mesmo um quântico) iria conter, mas ainda assim, máquinas pós-seletivas são interessantes sob uma perspectiva teórica. Remover qualquer uma dessas duas funcionalidades (quanticidade e pós-seleção) de PostBQP resulta em uma das duas seguintes classes, sendo as duas subclasses de PostBQP: * BQP é a mesma que PostBQP apenas sem pós-seleção * BPPpath é a mesma que PostBPP exceto que ao invés de quântico, o algoritmo é randômico clássico (com pós-seleção) Adicionar parece fazer com que Máquinas de Turing Quântica fiquem muito mais poderosas: provou que PostBQP é equivalente a PP, uma classe que se acredita ser relativamente poderosa, enquanto que BQP não se sabe se até mesmo contém a classe aparentemente menor NP. Utilizando técnicas similares, Aaronson também provou que pequenas mudanças nas leis da computação quântica teriam efeitos significativos. Como exemplos específicos, sob quaisquer das duas seguintes mudanças, a "nova" versão de BQP se tornaria equivalente a PP: * se nós ampliarmos a definição de 'porta quântica' para incluir não apenas operações unárias mas também operações lineares, ou * se a probabilidade de medição de um estado base for proporcional a no lugar de para qualquer inteiro ímpar p > 2. (pt) |
| dbo:wikiPageID | 4787255 (xsd:integer) |
| dbo:wikiPageLength | 20009 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1077981774 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quantum_computer dbr:Scott_Aaronson dbc:Articles_containing_proofs dbr:Logical_conjunction dbr:Complexity_class dbr:Computational_complexity_theory dbr:Computational_problem dbr:BQP dbr:PP_(complexity) dbr:Quantum_Turing_machine dbr:Hadamard_gate dbr:Intersection_(set_theory) dbc:Probabilistic_complexity_classes dbc:Quantum_complexity_theory dbr:Chernoff_bound dbr:PostBQP dbr:Polynomial_time dbr:Majority dbr:Without_loss_of_generality dbr:Quantum_circuit dbr:Postselection dbr:Uniform_circuit_family dbr:Union_bound dbr:NP_(complexity_class) |
| dbp:wikiPageUsesTemplate | dbt:Math dbt:Mvar dbt:Pi dbt:Sup dbt:TOClimit dbt:Tmath dbt:Sans-serif dbt:Quantum_computing |
| dct:subject | dbc:Articles_containing_proofs dbc:Probabilistic_complexity_classes dbc:Quantum_complexity_theory |
| rdf:type | yago:Abstraction100002137 yago:Class107997703 yago:Collection107951464 yago:Group100031264 yago:WikicatProbabilisticComplexityClasses |
| rdfs:comment | En teoria de la complexitat, la classe de complexitat postBQP és el conjunt de tots els problemes que es poden solucionar amb temps polinòmic per una Màquina de Turing quàntica amb post-selecció amb un error fitat (en el sentit que l'algorisme és correcte almenys 2/3 de les vegades per totes les entrades). La post-selecció no es considera que sigui una característica realista per un ordinador (ni per un de quàntic), però des del punt de vista teòric són unes màquines interessants. (ca) In computational complexity theory, PostBQP is a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with postselection and bounded error (in the sense that the algorithm is correct at least 2/3 of the time on all inputs). Postselection is not considered to be a feature that a realistic computer (even a quantum one) would possess, but nevertheless postselecting machines are interesting from a theoretical perspective. (en) Em teoria da complexidade computacional, PostBQP é uma classe de complexidade que consiste de todos os problemas computacionais solúveis em tempo polinomial em uma Máquina de Turing quântica com e erro limitado (no sentido de que o algoritmo é correto ao menos em 2/3 das vezes para todas as entradas). Pós-seleção não é considerada uma funcionalidade que um computador realístico (mesmo um quântico) iria conter, mas ainda assim, máquinas pós-seletivas são interessantes sob uma perspectiva teórica. (pt) |
| rdfs:label | PostBQP (Complexitat) (ca) PostBQP (en) PostBQP (pt) |
| owl:sameAs | freebase:PostBQP yago-res:PostBQP wikidata:PostBQP dbpedia-ca:PostBQP dbpedia-pt:PostBQP https://global.dbpedia.org/id/4u41r |
| prov:wasDerivedFrom | wikipedia-en:PostBQP?oldid=1077981774&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:PostBQP |
| is dbo:knownFor of | dbr:Scott_Aaronson |
| is dbo:wikiPageRedirects of | dbr:PostBQP_=_PP dbr:PostBQP=PP |
| is dbo:wikiPageWikiLink of | dbr:Scott_Aaronson dbr:BPP_(complexity) dbr:BQP dbr:PP_(complexity) dbr:Quantum_Turing_machine dbr:Boson_sampling dbr:PostBQP dbr:PostBQP_=_PP dbr:Postselection dbr:PostBQP=PP |
| is foaf:primaryTopic of | wikipedia-en:PostBQP |