Jednorazowe kwantowe uderzenia

W artykule Kwantowe losowe spacery uderzają wykładniczo szybciej ( arXiv: quant-ph / 0205083 ) Kempe podaje pojęcie czasu uderzenia w spacery kwantowe (w hipersześcianie), które nie jest zbyt popularne w literaturze dotyczącej spacerów kwantowych. Jest on zdefiniowany w następujący sposób:

One-Shot Quantum Uderzanie Czas: Dyskretny czasie spaceru ma kwantowy $(T,p)$ One-Shot $(|\Psi_0\rangle,|\Psi^f\rangle)$ czas -hitting jeśli $|\langle\Psi^f|U^T|\Psi_0\rangle|^2 \geq p$ gdzie $|\Psi_0\rangle$ jest stan początkowy, $|\Psi^f\rangle$ jest stan docelowej, a $p>0$ to prawdopodobieństwo trafienia.

Zwykle chciałbyś znać minimalną $T$ taką, że $p>0$ . Nie jest możliwe (popraw mnie, jeśli się mylę) zdefiniowanie pojęcia średniego czasu uderzenia, ponieważ będziesz musiał wykonać pomiary podczas marszu, a to doprowadziłoby to do klasycznego marszu. Właśnie dlatego mamy pojęcie jednorazowe. W tym samym dziele znajduje się aplikacja do routingu kwantowego (por. Sekcja 5 ).

Aby wiedzieć, że marsz dotarł do wierzchołka docelowego, musisz wykonać pomiar tylko w tym węźle. Na przykład w $n$ wymiarowym hipersześcianie z $2^n$ węzłami, jeśli zaczynasz od węzła $|\Psi_0\rangle=|00\dots00\rangle$ i mają jako węzła docelowego $|\Psi^f\rangle=|11\dots11\rangle$ , pokazuje papierowych $T=O(n)$ z ograniczonym prawdopodobieństwem błędu, to jest $p\to 1$ a $n$staje się bardzo duży. Aby więc wykryć, że spacer dotarł $|11\dots11\rangle$ dokonywania pomiaru po $\Omega(n)$ krokach. To jest wykładnicze przyspieszenie.

Pytania:

1. Aby użyć tego pojęcia czasu trafienia do wyszukiwania, musisz znać przynajmniej odległość wierzchołka docelowego od początku, ponieważ dzięki temu wiesz, kiedy zastosować swój pomiar. Powiedzmy, że masz wykres i ustaw jako początkowy wierzchołek v 0 i chcesz osiągnąć v f . Załóżmy również, że T = O ( d Jestem s t ( V 0 , V f ) ) i str ≥ 1 / 2 . Cóż, $G$$v_0$$v^f$$T=O(dist(v_0,v^f))$$p\geq 1/2$$T$jest oczywiste, ponieważ do osiągnięcia tego potrzeba co najmniej tylu kroków. Czy sensowne jest wykorzystywanie czasu trafień do wyszukiwania? Jeśli wiesz, gdzie jest węzeł, nie ma sensu w wyszukiwaniu, ale posiadanie informacji takich jak „odległość od wierzchołka początkowego”, ale nie wiedząc dokładnie, gdzie jest cel, to czy pojęcie czasu uderzenia daje jakieś interesujące (warto przestudiować ) algorytm wyszukiwania?

2. Czy zastosowanie do routingu kwantowego ma jakiś sens? W artykule napisano, że można go wykorzystać do routingu paczek, ale wydaje mi się, że możesz wysłać tylko 1 bit, np. Czy dotarł do miejsca docelowego, czy nie? Czy rzeczywiście możesz wysłać stan kwantowy w tych ramach? W artykule problem ten nie został rozwiązany.

3. Być może jest to głupie pytanie, ale proszę bardzo. Czy możesz użyć tego pojęcia czasu uderzenia do skonstruowania „Uogólnionego interferometru Macha-Zendera”?

Zdaję sobie sprawę z innych pojęć czasów uderzeń w spacery kwantowe (takich jak Szegedy lub Ambainis ). Szczególnie interesuje mnie ten konkretny czas uderzenia.

Aktualizacja (24.09.2010): Dzięki Joe Fitzsimons na pytania 2 i 3 udzielono pełnej odpowiedzi. Chociaż pytanie numer 1 wciąż pozostaje. Najpierw powtórzę pytanie 2 bardziej szczegółowo, kiedy skończyłem czytać artykuł, który Joe polecił mi i kilka innych (na przykład patrz arXiv: 0802.1224 ), a następnie podam konkretny przykład tego, co mam na myśli na pytanie 1.

2 '. Jeśli wysyłasz konkretną wiadomość (np. Sekwencję klasycznych bitów), możesz użyć bardziej skomplikowanej jednostki, która skopiuje te informacje podczas kroków marszu. Aby wysłać stany kwantowe, potrzebujesz czegoś więcej. Kanał łańcuchów spinowych wykorzystuje liniowy układ kubitów ze stałym sprzężeniem. Możesz umieścić stan (stan czysty, nie wiem, czy to działa dla stanów mieszanych), który chcesz przesłać na jednym końcu, i idzie na drugi koniec z wysoką wiernością zgodnie z wynikami liczbowymi. Nadal muszę się nad tym zastanowić, ale mam dwa pomysły: i) umieść łańcuch na każdym ogniwie wykresu, lub ii) przejdź się, znajdź stan docelowy, a następnie ustaw kanał między stanem początkowym a docelowym, a następnie wyślij Stan. Czy któreś z tych podejść jest prawdopodobne? Czy to działa ze stanami mieszanymi?

1 ”. Rozważmy spacer po dwuwymiarowej siatce wyśrodkowanej na początku z węzłami z każdej strony o długości $n$ . Ustaw stan początkowy nav0=(0,0),a stan docelowy navf=($\sqrt{n}$$v_0=(0,0)$gdziea=0,…,$v^f=(\sqrt{n}-1,a)$. Ponieważ marsz jest symetryczny, mamy taki sam czas trafienia i prawdopodobieństwo trafienia dla dowolnego celu gdzieś na granicy siatki, jak pokazano poniżej.$a=0,\dots,\sqrt{n}-1$

$dist(v_0,v^f)=\Omega(\sqrt{n})$$\Omega(\sqrt{n})$$O(\sqrt{n\log n})$$\sqrt{n\log n}$

Nie znam się tak dobrze na tym artykule, ale spróbuję udzielić szorstkiej odpowiedzi na każde z twoich pytań po pobieżnym przejrzeniu.

1. $O(\mbox{dist}(v_0, v^f))$$O(\sqrt{n})$$T=O(\mbox{dist}(v_0, v^f))$
2. Zakładam, że autor bierze cały pakiet na losowy spacer. Oczywiście wymaga to nieco bardziej skomplikowanej jednolitości, ale tak naprawdę nie widzę problemu. Alternatywnie, Burgarth i Bose mają bardzo ładny schemat kodowania informacji na identycznych wykresach, który również działałby, gdyby po prostu zastąpić ich łańcuchy 1d wybraną siecią ( quant-ph / 0406112 ).
3. Cóż, nie potrzebujesz tego pojęcia czasu uderzenia. Hipersześciany mają doskonały transfer stanu (patrz na przykład quant-ph / 0309131 i quant-ph / 0411020 ), dzięki czemu można zobaczyć transport na hipersześcianie jako interferometr z interferometrem Mach-Zender odpowiadającym przypadkowi 2d.

AKTUALIZACJA: (Aby odpowiedzieć na zaktualizowane pytanie dotyczące losowych spacerów po siatce lub innej sieci)

$v_t$$v^f$

W odniesieniu do pytania 1, znajomość odległości między nieznanym wierzchołkiem docelowym a niektórymi wierzchołkami znanego pochodzenia w hipersześcianie może pomóc w procesie wyszukiwania. Jednak wartość samej odległości określa, jak bardzo pomocne są te informacje.

Typowymi algorytmami chodzenia kwantowego są zwykle odmiany / aproksymacje poszukiwania Grovera: obejmują one przybliżony obrót wektora stanu w 2-wymiarowej podprzestrzeni całkowitej przestrzeni Hilberta.

Możesz użyć tych algorytmów, aby skutecznie przygotować w przybliżeniu równomierną superpozycję wszystkich wierzchołków w danej odległości od początku. Następnie możesz przeszukać swój docelowy wierzchołek wewnątrz tej superpozycji za pomocą wyszukiwania kwantowego lub klasycznego (Monte Carlo): W przypadku klasycznego wyszukiwania po prostu przygotuj superpozycję i zmierz ją w podstawie wierzchołka i powtarzaj, aż znajdziesz cel. W przypadku wyszukiwania kwantowego procedura przygotowania superpozycji (i jej odwrotność) staje się podprogramem, który zastępuje transformację Hadamarda w iteracji Grovera.

$n$$d$$\binom{n}{d}$$\approx \frac{2^n}{\sqrt{\frac{\pi}{2}n}}$$\approx n/2$