Utformningen av nya kvantalgoritmer har visat sig vara en mycket svår uppgift. I detta dokument behandlas problemet på ett annat sätt genom att man studerar problemet med "kvantstatsgeneration". Vi visar först att eventuella problem i statistisk nollkunskap (inklusive t.ex. diskret log, quadratic residuosity och gap närmaste vektor i en lattice) kan reduceras till en instans av quantum state generation problem. Efter att ha visat hur allmänt problemet med statsgenerationen är lade vi grunden till ett nytt paradigm för kvantstatsgenerationen. Vi definierar "Adiabatic State Generation" (ASG), som är baserad på Hamiltonians istället för enhetliga portar. Vi utvecklar verktyg för ASG inklusive en mycket allmän metod för att genomföra Hamiltonians (The glese Hamiltonian lemma), och sätt att garantera icke försumbara spektral luckor (Den taggiga adiabatic path lemma). Vi bevisar också att ASG är lika vid makten som tillståndsgenerering i standardkvantmodellen. Efter att ha lagt grunden för ASG visar vi hur vi kan tillämpa våra tekniker för att generera intressanta superpositioner relaterade till Markovkedjor. ASG-metoden för kvantalgoritmer ger spännande kopplingar mellan kvantberäkning och många olika områden: analys av spektralluckor och grundtillstånd av Hamiltonianer i fysik, snabbt blanda Markov kedjor, statistisk noll kunskap, och kvant random promenader. Vi hoppas att dessa länkar kommer att ge nya insikter och metoder i kvantalgoritmer.
Aharonov och Ta-Shma REF studerade också kvanttillståndsgenereringens beräkningskomplexitet och visade relationer mellan kvantadiabatdata, statistisk nollkunskap och kvanttillståndsgenerering.
Adiabatic quantum state generation and statistical zero knowledge
{'venue': "STOC '03", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics', 'Physics']}