Vi undersöker Goldreich-Levin Theorem i samband med kvantinformation. Detta resultat är en minskning från beräkningsproblemet att vända en enkelriktad funktion till problemet med att förutsäga en viss bit som är förknippad med den funktionen. Vi visar att kvantversionen av minskningen-mellan kvant enkelriktade funktioner och kvanthårdpredikat-är kvantitativt mer effektiv än den kända klassiska versionen. Ungefär, om enkelriktad funktion fungerar på n-bitars strängar då overhead i minskningen är med en faktor av O(n/ε 2 ) i det klassiska fallet men endast med en faktor av O(1/ε) i kvantfallet, där 1 2 + ε är sannolikheten för att förutsäga svår predikat. Dessutom visar vi via en lägre gräns att den klassiska versionen av reduktionen i en svart låda inte kan ha en övre gräns som är mindre än  och 2. Vi visar också att man med hjälp av denna minskning kan få ett kvantbitsengagemang som är helt bindande och beräkningsmässigt döljande från vilken kvantenkel permutation som helst. Detta kompletterar ett nytt resultat av Dumais, Mayers och Salvail, där biten engagemang system är perfekt dölja och beräkningsmässigt bindande. Vi visar också hur man utför ett qubit-åtagande genom ett liknande tillvägagångssätt.
Resultatet av REF visar att denna minskning kan uppnås effektivare när man överväger kvantfunktioner och kvanthårdpredikat.
A quantum Goldreich-Levin theorem with cryptographic applications
{'venue': 'In Proc. of STACS ’02, LNCS 2285', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Physics', 'Computer Science']}