QMA

Vuonna laskennan vaativuus, QMA, joka tarkoittaa Quantum Merlin Arthur, on kvantti analogi deterministinen kompleksisuusluokka NP tai todennäköisyyksiin kompleksisuusluokka MA. Se liittyy BQP samalla tavalla NP, jotka liittyvät P, tai MA liittyy BPP.

Epävirallisesti, se on joukko päätöksen ongelmia, joihin, kun vastaus on kyllä, on polynomi-size kvantti todiste joka vakuuttaa polynomiaikainen kvantti todentajan siitä suurella todennäköisyydellä. Lisäksi kun vastaus on ei, jokainen polynomi-size kvanttitilassa hylkää todentajan suurella todennäköisyydellä.

Tarkemmin, todisteita on oltava todennettavissa polynomisessa aikaa kvanttitietokoneen, niin että jos vastaus on todellakin KYLLÄ, todentaja hyväksyy oikea todiste todennäköisyydellä yli 2/3, ja jos vastaus on ei, sitten on mitään todisteita joka vakuuttaa todentaja hyväksyä todennäköisyydellä alle kolmasosa. Kuten tapana on, vakiot 2/3 ja 1/3 voidaan muuttaa. Muuttuvat 2/3 Jonkin jatkuvasti tiukasti välillä 1/2 ja 1, tai muuttamalla 1/3 Jonkin jatkuvasti tarkasti välillä 0 ja 1/2, ei muuta luokan QMA.

QAM on liittyvä kompleksisuusluokka, jossa kuvitteellinen aineet Arthur ja Merlin suorittaa järjestyksessä: Arthur luo satunnainen merkkijono, Merlin vastauksia kvantti todistus ja Arthur todentaa sen BQP kone.

Määritelmä

Kieli L on jos on olemassa polynomi aika kvantti todentaja V ja polynomi p siten, että:

  • On olemassa kvanttitilassa siten, että todennäköisyys, että V-hyväksyy syötteen on suurempi kuin.
  • Kaikkien kvanttitilojen, todennäköisyys, että V hyväksyy tulo on alle.

jossa vaihtelee kaikkien kvantti valtioiden korkeintaan s qubits.

Kompleksisuusluokka määritellään olevan sama. Kuitenkin, vakiot eivät ole liian tärkeää, koska luokan pysyy muuttumattomana jos ja on asetettu mitään vakioita siten, että on suurempi kuin. Lisäksi mistään polynomeja ja meillä on

Ongelmia QMA

Koska monia mielenkiintoisia luokkiin sisältyvät QMA, kuten P, BQP ja NP, kaikki ongelmat nämä luokat ovat myös QMA. On kuitenkin olemassa ongelmia, jotka ovat QMA, mutta ei tiedetä olevan NP tai BQP. Jotkut tällaiset hyvin tunnettuja ongelmia käsitellään jäljempänä.

Ongelma sanotaan olevan QMA-kova, analoginen NP-kova, jos jokainen ongelma QMA voidaan pienentää sitä. Ongelma sanotaan olevan QMA-täydellinen, jos se on QMA-kova ja QMA.

Paikallinen Hamiltonin ongelma

Paikallinen Hamiltonin ongelma on kvantti analoginen MAX-SAT. Hamiltonin on hermiittinen matriisi toimii kvanttitilojen, joten se on järjestelmä n qubits. K-paikallinen Hamiltonin on Hamiltonin, joka voidaan kirjoittaa summana Hamiltonians, joista kukin toimii kuin triviaalisti on korkeintaan k kvanttibittejä.

K-paikallinen Hamiltonin ongelma, joka on lupauksen ongelma, määritellään seuraavasti. Tulo on K-paikallinen Hamiltonin toimiva n qubits, joka on summa polynomisesti monet hermiittinen matriiseja, jotka toimivat vain k qubits. Panos sisältää myös kaksi numeroa, niin että jollain vakiolla c. Ongelmana on, onko pienimmän ominaisarvon tämän Hamiltonin on vähemmän kuin tai suurempi kuin b, lupasi, että yksi näistä on kyse.

K-paikallinen Hamiltonin on QMA-täydellinen k ≥ 2.

QMA-kovuus tulokset tunnetaan jopa yksinkertainen ja fyysisesti realistinen ristikko malleja qubits kuten missä ovat Paulin matriiseja. Tällaiset mallit ovat sovellettavissa yleismaailmallisia adiabaattiseen kvanttilaskentaan.

Hamiltonians varten QMA-täydellinen ongelma voidaan rajoittaa toimimaan kaksiulotteinen ruudukko qubits tai linja kvantti hiukkasia 12 valtioiden hiukkasta kohti.

Muut QMA-täydelliset ongelmat

Luettelon tunnetuista QMA-täydelliset ongelmat löytyvät luokista

QCMA, joka tarkoittaa Quantum Klassinen Merlin Arthur, on samanlainen QMA, mutta todisteet on oltava klassisen merkkijono. Ei tiedetä, onko QMA vastaa QCMA, vaikka QCMA on selvästi sisältyvät QMA.

QIP, joka tarkoittaa Quantum Interactive polynomiajassa, on yleistys QMA jossa Merlin ja Arthur olla vuorovaikutuksessa k kierroksilla. QMA on QIP. QIP tiedetään olevan PSPACE.

QIP on QIP jossa k saa olla polynomi määrän kvanttibittejä. On tunnettua, että QIP = QIP. On myös tunnettua, että QIP = IP-= PSPACE.

Suhde muihin luokkiin

QMA liittyy muihin tunnettuihin monimutkaisuuden luokkiin seuraavasti suhteet:

Ensimmäinen sisällyttäminen määritelmästä seuraa NP. Seuraavat kaksi sulkeumia seuraa siitä, että todentaja tehdään tehokkaampi kussakin tapauksessa. QCMA sisältyy QMA koska todentaja voi pakottaa prover lähettää klassista todiste mittaamalla todisteita heti ne vastaanotetaan. Se, että QMA sisältyy PP osoitettiin Alexei Kitaev ja John Watrous. PP on myös helposti osoitettu olevan PSPACE.

Ei tiedetä, jos jokin näistä sulkeumat on tiukka. Se ei edes tiedetä, P on ehdottomasti sisältyvät PSPACE tai P = PSPACE.

Edellinen artikkeli Queen Hyde Park 1976
Seuraava artikkeli Qué bonito Amor