About: QIP (complexity)     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatProbabilisticComplexityClasses, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon
http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FQIP_%28complexity%29

In computational complexity theory, the class QIP (which stands for Quantum Interactive Polynomial time) is the quantum computing analogue of the classical complexity class IP, which is the set of problems solvable by an interactive proof system with a polynomial-time verifier and one computationally unbounded prover. Informally, IP is the set of languages for which a computationally unbounded prover can convince a polynomial-time verifier to accept when the input is in the language (with high probability) and cannot convince the verifier to accept when the input is not in the language (again, with high probability). In other words, the prover and verifier may interact for polynomially many rounds, and if the input is in the language the verifier should accept with probability greater than

AttributesValues
rdf:type
rdfs:label
  • QIP (Complexitat) (ca)
  • QIP (complexity) (en)
rdfs:comment
  • En teoria de la complexitat, la classe de complexitat QIP és la classe quàntica anàloga a la classe de complexitat IP, que és el conjunt de problemes que es poden resoldre per un sistema de demostració interactiu amb un verificador de temps polinòmic i un demostrador sense restriccions. (ca)
  • In computational complexity theory, the class QIP (which stands for Quantum Interactive Polynomial time) is the quantum computing analogue of the classical complexity class IP, which is the set of problems solvable by an interactive proof system with a polynomial-time verifier and one computationally unbounded prover. Informally, IP is the set of languages for which a computationally unbounded prover can convince a polynomial-time verifier to accept when the input is in the language (with high probability) and cannot convince the verifier to accept when the input is not in the language (again, with high probability). In other words, the prover and verifier may interact for polynomially many rounds, and if the input is in the language the verifier should accept with probability greater than (en)
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • En teoria de la complexitat, la classe de complexitat QIP és la classe quàntica anàloga a la classe de complexitat IP, que és el conjunt de problemes que es poden resoldre per un sistema de demostració interactiu amb un verificador de temps polinòmic i un demostrador sense restriccions. De manera informal, la classe IP és el conjunt de llenguatges els quals un demostrador sense restriccions pot convèncer un verificador per acceptar si l'entrada és del llenguatge (amb molta probabilitat) i no pot convèncer-lo per acceptar si l'entrada no pertany al llenguatge (de nou, amb alta probabilitat). A IP, el verificador és una màquina com les de la classe BPP; a QIP, la comunicació entre el demostrador i el verificador és quàntica i el verificador pot realitzar operacions quàntiques. En aquest cas, el verificador és com una màquina BQP. (ca)
  • In computational complexity theory, the class QIP (which stands for Quantum Interactive Polynomial time) is the quantum computing analogue of the classical complexity class IP, which is the set of problems solvable by an interactive proof system with a polynomial-time verifier and one computationally unbounded prover. Informally, IP is the set of languages for which a computationally unbounded prover can convince a polynomial-time verifier to accept when the input is in the language (with high probability) and cannot convince the verifier to accept when the input is not in the language (again, with high probability). In other words, the prover and verifier may interact for polynomially many rounds, and if the input is in the language the verifier should accept with probability greater than 2/3, and if the input is not in the language, the verifier should be reject with probability greater than 2/3. In IP, the verifier is like a BPP machine. In QIP, the communication between the prover and verifier is quantum, and the verifier can perform quantum computation. In this case the verifier is like a BQP machine. By restricting the number of messages used in the protocol to at most k, we get the complexity class QIP(k). QIP and QIP(k) were introduced by John Watrous, who along with Kitaev proved in a later paper that QIP = QIP(3), which shows that 3 messages are sufficient to simulate a polynomial-round quantum interactive protocol. Since QIP(3) is already QIP, this leaves 4 possibly different classes: QIP(0), which is BQP, QIP(1), which is QMA, QIP(2) and QIP. Kitaev and Watrous also showed that QIP is contained in EXP, the class of problems solvable by a deterministic Turing machine in exponential time. QIP(2) was then shown to be contained in PSPACE, the set of problems solvable by a deterministic Turing machine in polynomial space. Both results were subsumed by the 2009 result that QIP is contained in PSPACE, which also proves that QIP = IP = PSPACE, since PSPACE is easily shown to be in QIP using the result IP = PSPACE. (en)
gold:hypernym
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is Wikipage redirect of
is Wikipage disambiguates of
is known for of
is known for of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 59 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software