Dowody kwantowe klasycznych twierdzeń

Interesują mnie przykłady problemów, w których twierdzenie, które pozornie nie ma nic wspólnego z mechaniką / informacją kwantową (np. Mówi coś o obiektach czysto klasycznych), może jednak zostać udowodnione za pomocą narzędzi kwantowych. Badanie Kwantowe dowody dla klasycznych twierdzeń (A. Drucker, R. Wolf) podaje ładną listę takich problemów, ale na pewno jest ich o wiele więcej.

Szczególnie interesujące byłyby przykłady, w których dowód kwantowy jest nie tylko możliwy, ale także „bardziej pouczający”, analogicznie do rzeczywistej i złożonej analizy, gdzie umieszczenie prawdziwego problemu w złożonym otoczeniu często czyni go bardziej naturalnym (np. Geometria jest prostsza, ponieważ jest algebraicznie zamknięty itp.); innymi słowy, klasyczne problemy, dla których świat kwantowy jest ich „naturalnym środowiskiem”.$\mathbb{C}$

(Nie definiuję tutaj „kwantowości” w żadnym konkretnym sensie i można argumentować, że wszystkie takie argumenty ostatecznie sprowadzają się do algebry liniowej; cóż, można również przetłumaczyć dowolny argument za pomocą liczb zespolonych, aby użyć tylko par liczb rzeczywistych - ale co z tego ?)

Jest ostatni artykuł Scotta Aaronsona, który stanowi nowy dowód na to, że permanent jest twardy. Dowód ten opiera się na modelu liniowo-optycznego obliczenia kwantowego i jest bardziej intuicyjny niż Leslie Valiant.

Moim zdaniem podoba mi się następujący artykuł:

Katalin Friedl, Gabor Ivanyos, Miklos Santha. Skuteczne testowanie grup. W STOC'05.

Tutaj definiują „klasyczny” tester dla grup abelowych. Najpierw jednak zaczynają od podania testera kwantowego, a następnie eliminują wszystkie części kwantowe.

W tym artykule podoba mi się to, że używają testera kwantowego, aby uzyskać intuicję i używać go do podejścia do problemu. Może to brzmieć trudniej (zacznij od kwantowej i przejdź do klasycznej), ale autorzy są znanymi badaczami w dziedzinie obliczeń kwantowych. Więc może dla nich łatwiej zacząć od tego.

Powiedziałbym, że ich głównym wkładem technicznym jest tester homomorfizmu, którego używają do eliminacji części kwantowych.

Dwa bardzo aktualne i interesujące wyniki:

• Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary i Ronald de Wolf udowodnili, że „nie istnieje program liniowy wielomianowy (LP), który wiązałby projekty polytopowe z polytopem wędrownego sprzedawcy, nawet jeśli nie jest wymagana symetryczność LP „(cytowany z streszczenia).
  Wykorzystują złożoność komunikacji kwantowej jako narzędzie. Zobacz ich artykuł i post na blogu Gil Kalai . Zwróć także uwagę na komentarz Dave'a pod postem Gila Kalai. Nie przeczytałem jeszcze tego artykułu, więc nie mogę komentować, gdzie i jak wykorzystywane są kwantowe rzeczy.

• Andrew M. Childs, Shelby Kimmel i Robin Kothari zastosowali kwantową złożoność zapytań, aby udowodnić dolne granice dla bardzo klasycznej miary, która jest bramką formuły funkcji takich jak PARITY. Zobacz ich artykuł .

Ponieważ stałe dają amplitudy prawdopodobieństwa wyników pomiarów bozonów po tym, jak ingerują w interferometr liniowy, Scheel uzyskał prosty „kwantowy” dowód, że wartość bezwzględna stałej dowolnej macierzy jednolitej wynosi 1 ( http://arxiv.org/abs / quant-ph / 0406127 ).

• patrz także informatyka klasyczna obejmuje idee kwantowe jako rodzaj półpopularyzacyjnego przeglądu / ankiety tego klasycznego / kwantowego zjawiska dychotomii autorstwa Wolchovera dla Instytutu Simonsa z kilkoma przykładami i wskazówkami / referencjami.

W ostatnich latach pomysły kwantowe pomogły naukowcom udowodnić bezpieczeństwo obiecujących schematów szyfrowania danych zwanych kryptosystemami opartymi na sieciach, których niektóre aplikacje mogą osłaniać wrażliwe informacje użytkowników, takie jak DNA, nawet od firm, które je przetwarzają. Dowód obliczeń kwantowych doprowadził również do formuły minimalnej długości kodów korygujących błędy, które są zabezpieczeniami przed uszkodzeniem danych.

Pomysły kwantowe zainspirowały również szereg ważnych wyników teoretycznych, takich jak odrzucenie starego, błędnego algorytmu, który twierdził, że skutecznie rozwiązuje słynny trudny problem sprzedawcy podróżującego, który pyta, jak znaleźć najszybszą trasę przez wiele miast.

• kolejny niedawny przykład podobny do kierunku badań naturalnych dowodów Razborova / Rudicha (który powiązał separacje klas złożoności z łamaniem generatorów liczb losowych)

Kwantowa dolna granica dla odróżnienia funkcji losowych od losowych permutacji Henry Yuen

Problem rozróżnienia funkcji losowej od przypadkowej permutacji w domenie o rozmiarze N jest ważny w kryptografii teoretycznej, w której bezpieczeństwo wielu prymitywów zależy od twardości problemu. Badamy złożoność kwantową tego problemu ...