Vi introducerar en ny kvantmottagarmetod för att bevisa lägre gränser på frågekomplexet i kvanttillståndsgenereringsproblemet. Detta problem omfattar både beräkning av partiella eller totala funktioner och förberedelse av mål kvanttillstånd. Det har under ganska lång tid funnits hopp om att kvanttillståndsgenerering kan vara en väg att ta itu med problemet med grafen Isomorfism. Vi visar att för det relaterade problemet med Index Erasure vår metod leder till en lägre gräns av  och som matchar en övre gräns som erhållits genom reduktion till kvantsökning på N element. Detta avslutar ett öppet problem som först togs upp av Shi [FOCS'02]. Vår strategi bygger på två idéer: (i) å ena sidan generaliserar vi de kända additiva och multiplikativa motmetoderna till fallet med kvantstatsgenerering, (ii) å andra sidan visar vi hur symmetrierna i det underliggande problemet kan utnyttjas för utformningen av optimala motståndare matriser och dramatiskt förenkla beräkningen av motståndarens gränser. Tillsammans ger dessa två idéer det nya resultatet för Index Erasure genom att använda representationsteorin för den symmetriska gruppen. Dessutom kan metoden leda till lägre gränser även för små framgångsannolikhet, i motsats till standard motståndare metod. Dessutom besvarar vi en öppen fråga på grund av Špalek [CCC'08] genom att visa att den multiplikativa versionen av motståndaren metoden är starkare än den additiva för något problem. Slutligen bevisar vi att den multiplikativa bundet uppfyller en stark direkt produkt teorem, utvidgar ett resultat av Spalek till kvanttillstånd generation problem.
Frågan komplexitet kvanttillståndsgenerering problem studerades i REF, där motståndaren metoden utvidgades till denna modell och användes för att bevisa en snäv lägre gräns på en specifik kvanttillståndsgenerering problem som kallas IndexErasure.
Symmetry-assisted adversaries for quantum state generation
{'venue': "26th IEEE Conference on Computational Complexity (CCC'11), pages 167-177, 2011", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Physics', 'Mathematics']}