Czy istnieje odpowiednik derandomizacji dla algorytmów kwantowych?

W przypadku niektórych algorytmów randomizowanych można go zdemandomizować, usuwając (przy możliwym koszcie w czasie wykonywania) użycie bitów losowych i maksymalizując pewną dolną granicę celu (zwykle obliczaną na podstawie faktu, że twierdzenia dotyczą oczekiwanej wydajności losowej algorytm). Czy istnieje odpowiednik algorytmów kwantowych? Czy są jakieś dobrze znane wyniki „dekwantyzacji”? A może podstawowa przestrzeń stanu jest zbyt duża dla tego rodzaju techniki?

W tym temacie pojawił się post na blogu autorstwa Fortnow . Uważa się, że nie ma nadziei na program „dekwantyzacji”, podobny do programu derandomizacji.

Z drugiej strony, w przypadku niektórych konkretnych wyników nie kwantowych uzyskanych metodami kwantowymi możliwe było usunięcie kwantowości z dowodu. Na przykład Kerenidis i de Wolf (2002) udowodnili pierwszą wykładniczą dolną granicę długości możliwie nieliniowych 2-kwerendowych kodów dekodowanych lokalnie przy użyciu argumentów kwantowych. Później Ben-Aroya, Regev i de Wolf (2007) mogli usunąć kwantowość dowodu (chociaż linia argumentacji nadal modelowała kwantową). Podobne sytuacje pojawiły się również w dowodzeniu dolnych granic sztywności macierzy Hadamarda oraz w wykazywaniu, że PP jest zamknięty pod przecięciem (choć w odwrotnej kolejności chronologicznej :)). Zobacz tę ankietę Druckera i de Wolfa w celu uzyskania referencji i dyskusji.

Istnieją pewne klasy bram kwantowych, które można skutecznie symulować za pomocą klasycznego komputera. Jeśli nie występuje splątanie, można skutecznie symulować obliczenia ze stanami czystymi (tj. Nie przypadkowymi). Klasyczne bramki Odwracalne bramki są podzbiorem bram kwantowych, a zatem można je oczywiście skutecznie symulować. Te dwa przykłady są dość trywialne, jednak znanych jest wiele nietrywialnych zestawów bramek.

1. Dzielne bramy, jak wspomniano w odpowiedzi Jozuego
2. Bramy grupy Clifford (patrz arXiv: quant-ph / 0406196 )
3. Dopasuj bramki (patrz arXiv: 0804.4050 )
4. Bramy dojazdy itp.

$SU(2^N)$$SU(2^N)$

Wydaje się bardzo mało prawdopodobne, aby mechanika kwantowa była efektywnie symulowalna, dlatego taki program dekwantyzacji będzie prawdopodobnie ogólnie niemożliwy. Istnieje jednak reżim, w którym to działało, a mianowicie z interaktywnymi dowodami. Wykazano, że kilka różnych rodzajów interaktywnych systemów dowodowych z weryfikatorami kwantowymi ma tę samą moc, jeśli weryfikator kwantowy zostanie zastąpiony czysto klasycznym weryfikatorem. Przykład tego można znaleźć w dowodach Jaina, Ji, Upadhyaya i Watrousa, że ​​QIP = PSPACE ( arXiv: 0907.4737 ).

Interesującym miejscem, w którym można studiować „dekwantyzację”, jest złożoność komunikacji. Tutaj interesujące jest pytanie, czy górną granicę można ustalić na poziomie splątania, które Alice i Bob muszą dzielić, aby osiągnąć skuteczny protokół kwantowy do rozwiązania jakiegoś problemu. Byłby to kwantowy analog twierdzenia Newmana z klasycznej złożoności komunikacji. Gavinsky podał problem relacyjny, dla którego nie można tego zrobić, ale o ile wiem, wciąż jest otwarty na (całkowite) problemy funkcjonalne.

Ponadto dodatek do komentarza Joe na temat bram dojeżdżania do pracy: Bremner, Jozsa i Shepherd niedawno pokazali (arXiv: 1005.1407), że mało prawdopodobne jest, aby określone pojęcie obwodów dojazdów do pracy było możliwe do symulacji, ponieważ doprowadziłoby to do upadku hierarchii wielomianowej na trzeci poziom.

Chociaż generalnie „dekwantyzacja” jest mało prawdopodobna, uważam, że ten pomysł pomógł zainspirować holograficzne algorytmy Valiant. Albo przynajmniej możesz zobaczyć jego pracę jako wyniki częściowej dekwantyzacji w ograniczonych klasach obwodów kwantowych. Patrz na przykład: L. Valiant. Obwody kwantowe, które można symulować klasycznie w czasie wielomianowym. SIAM J. Comput. 31 (4) 1229-1254 (2002).