Próbkowanie w przybliżeniu z wypukłych wielościanów za pomocą komputerów kwantowych

Komputery kwantowe są bardzo dobre do dystrybucji próbkowania, których nie wiemy jak próbkować przy użyciu klasycznych komputerów. Na przykład, jeśli f jest funkcją logiczną (od do ), którą można obliczyć w czasie wielomianowym, to za pomocą komputerów kwantowych możemy skutecznie próbkować zgodnie z rozkładem opisanym przez Rozwinięcie Fouriera f. (Nie wiemy, jak to zrobić z klasycznymi komputerami).$\{-1,1\}^n$${-1,1}$

Czy możemy użyć komputerów kwantowych do próbkowania lub przybliżenia próbki losowego punktu w wielościanie opisanego przez system n nierówności w zmiennych d?

Przejście od nierówności do punktów wydaje mi się nieco podobne do „transformacji”. Co więcej, chętnie zobaczę algorytm kwantowy, nawet jeśli zmodyfikujesz rozkład, np. Rozważ iloczyn rozkładu Gaussa opisanego przez hiperpłaszczyzny wielościanu lub kilka innych rzeczy.

Kilka uwag: Dyer, Frieze i Kannan znaleźli słynny klasyczny algorytm wielomianu czasowego, aby w przybliżeniu próbkować i w przybliżeniu obliczać objętość wielościanu. Algorytm oparty jest na losowych spacerach i szybkim mieszaniu. Chcemy więc znaleźć inny algorytm kwantowy do tego samego celu. (OK, możemy mieć nadzieję, że algorytm kwantowy może również prowadzić do rzeczy w tym kontekście, o których nie wiemy, że robimy to klasycznie. Ale na początek chcemy tylko innego algorytmu, to musi być możliwe.)

Po drugie, nawet nie nalegamy na próbkowanie w przybliżeniu jednolitego rozkładu. Z przyjemnością w przybliżeniu spróbujemy innej fajnej dystrybucji, która jest z grubsza wspierana na naszym wielościanie. Argument Santosha Vampali (a także mnie w innym kontekście) prowadzi od próbkowania do optymalizacji: jeśli chcesz zoptymalizować próbkę f (x), aby znaleźć punkt y, w którym f (x) jest typowy. Dodaj ograniczenie {f (x)> = f (y)} i powtórz.

Jak potwierdza post, istnienie klasycznego algorytmu wielomianowo-czasowego do oszacowania objętości wypukłego polytopa zmienia zasady gry. Algorytm kwantowy jest znacznie mniej interesujący, chyba że konkuruje z klasycznymi algorytmami. W końcu bez tego kryterium każdy klasyczny algorytm można po prostu nazwać algorytmem kwantowym.

To powiedziawszy, wciąż jest miejsce na przyspieszenie wielomianowe, a głównym znanym punktem widzenia dla tego rodzaju przyspieszenia jest marsz kwantowy, szczególnie biorąc pod uwagę, że klasyczne przyspieszenie w tym przypadku opiera się na dobrym chodzeniu losowym. (Rzeczywiście, każdy algorytm kwantowy może być postrzegany jako spacer kwantowy, ale w przypadku niektórych algorytmów niekoniecznie jest to pouczające). Różne prace w literaturze QC wskazują, że algorytmy do szacowania objętości wypukłego polytopa wykorzystują losowe spacery, i że może dojść do przyspieszenia ze spaceru kwantowego. Wygląda więc na to, że badacze znają tę sugestię, ale nikt nie próbował ustalić, jakie przyspieszenie wielomianowe można uzyskać dla tego problemu. Możesz nic nie dostać, jeśli najlepszy klasyczny algorytm ma jakiś spoiler,

Oto zbiór artykułów, w których wszystkie wspominają o podstawowej idei; ponownie Google Scholar wydaje się sugerować, że nikt nie poszedł dalej.

1. arXiv: quant-ph / 0104137 - Quantum Walks on the Hypercube
2. arXiv: quant-ph / 0205083 - Kwantowe losowe spacery uderzają wykładniczo szybciej
3. arXiv: quant-ph / 0301182 - Dekoherencja dyskretnych spacerów kwantowych
4. arXiv: quant-ph / 0304204 - Kontrola dyskretnych spacerów kwantowych: monety i stany początkowe
5. arXiv: quant-ph / 0411065 - Spacer kwantowy po linii z dwoma splątanymi cząsteczkami
6. arXiv: quant-ph / 0504042 - Uwikłanie w wymyślone spacery kwantowe na zwykłych grafach
7. arXiv: quant-ph / 0609204 - Kwantowe przyspieszenie klasycznych procesów mieszania
8. arXiv: 0804.4259 - Przyspieszenie poprzez próbkowanie kwantowe
9. Podejście losowe do algorytmów kwantowych
10. Dyskretny spacer kwantowy do rozwiązywania równań nieliniowych nad polami skończonymi

Drugą stroną klasycznych algorytmów do oszacowania objętości wypukłego politopu jest programowanie liniowe. Nie wiem, czy nastąpił postęp w znalezieniu przyspieszenia kwantowego. Wydaje się, że trudno jest uniknąć etapu programowania liniowego, aby umieścić wypukły polytop w dogodnej pozycji do próbkowania.