Czy możemy kwantyfikować „stopień kwantowości” w algorytmie kwantowym?

24

Splątanie jest często utrzymywane jako kluczowy składnik, który sprawia, że ​​algorytmy kwantowe są dobrze ... kwantowe, i można to prześledzić do stanów Bella, które niszczą ideę fizyki kwantowej jako modelu probabilistycznego w stanie ukrytym. W teorii informacji kwantowej (z mojego raczej słabego zrozumienia) splątanie może być również wykorzystane jako konkretny zasób, który ogranicza możliwość wykonywania pewnych rodzajów kodowania.

Ale z innych rozmów (ostatnio zasiadałem w komitecie doktora fizyka zajmującego się metodami kwantowymi) stwierdzam, że uwikłanie jest trudne do oszacowania, szczególnie w przypadku stanów kwantowych o mieszanym stanie. W szczególności trudno jest powiedzieć, że określony stan kwantowy zawiera X jednostek splątania (praca doktorska studenta dotyczyła ilościowej oceny ilości splątania „dodanego” przez dobrze znane operacje bramkowe). W rzeczywistości ostatnia praca doktorska sugeruje, że pojęcie zwane „niezgodą kwantową” może być również istotne (i potrzebne) do kwantyfikacji „kwantowości” algorytmu lub stanu.

Jeśli chcemy traktować splątanie jako zasób podobny do losowości, należy zapytać, jak zmierzyć, ile z tego jest „potrzebne” dla algorytmu. Nie mówię o całkowitej dekwantyzacji , a jedynie o sposobie pomiaru ilości.

Czy istnieje obecnie jakikolwiek zaakceptowany sposób pomiaru „kwantowości” stanu lub operatora, czy ogólnie algorytmu?

Suresh Venkat
źródło
1
Nie do końca to samo pytanie, ale Earl Campbell ma niezłą gazetę na temat wciągającej siły operatorów: arXiv: 1007: 1445
Joe Fitzsimons
1
Pojęcie niezgody kwantowej jest zdecydowanie ważne dla kwantyfikacji „kwantowości” splątania: prl.aps.org/abstract/PRL/v88/i1/e017901
Artem Kaznatcheev
Z drugiej strony nie jest wcale jasne, czy niezgoda pomaga w kwantyfikacji „kwantowości obliczeń”. Nie mogę podać odniesienia do tego, ale Van den Nest przedstawił negatywny argument przeciwko znaczeniu splątania w obliczeniach kwantowych, które stosuje się do ciągłych miar splątania; ten sam argument powinien uogólniać się na niezgodę.
Juan Bermejo Vega

Odpowiedzi:

24

To zależy od kontekstu.

  1. W przypadku algorytmów kwantowych sytuacja jest trudna, ponieważ jak wiemy, P = BPP = BQP. Dlatego nigdy nie możemy powiedzieć, że algorytm kwantowy robi coś, czego nie potrafi żaden klasyczny algorytm; tylko coś, z czym naiwna symulacja miałaby problem. Na przykład, jeśli obwód kwantowy jest rysowany jako wykres, wówczas istnieje klasyczna symulacja, która przebiega wykładniczo w czasie na szerokości wykresu ). Tak więc szerokość grzbietu można uznać za górną granicę „kwantowości”, chociaż nie jest to dokładna miara.

    Czasami mierzenie kwantowości w algorytmach jest mylone z próbą zmierzenia ilości splątania wytwarzanego przez algorytm, ale teraz uważamy, że hałaśliwy komputer kwantowy może mieć przewagi obliczeniowe w stosunku do klasycznego komputera, nawet przy tak dużym hałasie, że jego kubity nigdy nie są w stanie splątanym (np . jeden czysty model kubitowy ). Tak więc konsensus jest teraz bardziej po stronie myślenia o kwantowości w algorytmach kwantowych jako związanej raczej z dynamiką niż ze stanami generowanymi po drodze. To może pomóc wyjaśnić, dlaczego „dekwantyzacja” nie jest ogólnie możliwa.

  2. Dla dwustronnych stanów kwantowych, w których kontekstem są korelacje dwupartyjne, mamy wiele dobrych miar kwantowości. Wiele z nich ma wady, na przykład twardość NP lub brak addytywności, ale mimo to mamy dość wyrafinowane zrozumienie tej sytuacji. Oto ostatnia recenzja .

  3. Istnieją inne konteksty, na przykład gdy mamy stan kwantowy i chcielibyśmy wybierać między różnymi niezgodnymi pomiarami. W tym ustawieniu istnieją zasady niepewności, które mówią nam o tym, jak pomiary są niezgodne. Im bardziej niezgodne są pomiary, tym bardziej mamy do czynienia z sytuacją „kwantową”. Jest to związane między innymi z kryptografią i możliwościami zerowego błędu głośnych kanałów .
Aram Harrow
źródło
10

Odpowiedź Arama jest doskonała, więc proszę nie zabieraj mnie do publikowania odpowiedzi, ponieważ w każdym razie nie zgadzam się z tym, co powiedział, jedynie uzupełniając ją.

12000+1211113100+13010+13001

Jest to szczególnie istotne dla postawionego pytania, ponieważ wydaje się, że wykluczałoby jakąkolwiek monotoniczną miarę „kwantowości” opartą na miarach splątania.

Joe Fitzsimons
źródło
7

Bardziej złożony teoretyczny punkt widzenia można znaleźć w rozdz. 8 pracy R. Joszy Wprowadzenie do obliczeń kwantowych opartych na pomiarach . Stwierdza, co następuje:

Modele oparte na pomiarach zapewniają naturalny formalizm podziału algorytmu kwantowego na „części klasyczne i części kwantowe”.

Stwierdza także przypuszczenie o ilości „kwantowości” potrzebnej przez algorytm BQP:

O(logn)

Zobacz artykuł, aby uzyskać jasne wyjaśnienie warstwy kwantowej i ogólnie modelu. Hipoteza jest wciąż otwarta i wydaje mi się, że jest to dobry sposób na ilościowe określenie „kwantowości” algorytmu, przynajmniej od strony złożoności obliczeniowej.

Alessandro Cosentino
źródło