Splątanie jest często dyskutowane jako jeden z podstawowych składników, który odróżnia kwant od klasycznego. Ale czy splątanie jest naprawdę konieczne, aby przyspieszyć obliczenia kwantowe?

entanglement speedup

— DaftWullie
źródło

phys.org/news/2008-12-quantum-entanglement.html

— Steven Sagona

@StevenSagona Ten artykuł prasowy mówi o modelu DQC1. Tam jest zawsze uwikłanie w tym modelu, to po prostu, że naiwny Pierwsza analiza patrzy tylko na to w jednym konkretnym miejscu, gdzie okazuje się nie być .

— DaftWullie

Czy zadałeś i odpowiedziałeś na to pytanie z powodu mojej odpowiedzi na: quantumcomputing.stackexchange.com/a/2601/2293 ?

— user1271772,

@ user1271772 Nie! Chociaż zapytałem o to z powodu czegoś, co powiedziało mi jako komentarz, że potrzebuję pełniejszej odpowiedzi, do której mógłbym się odnieść.

— DaftWullie

@DaftWullie: Nie rozumiem, dlaczego moja odpowiedź ma 5 głosów negatywnych. Być może samo powiedzenie „uwikłanie jest uważane za wymóg QC” nie było wystarczające?

— użytkownik1271772,

Krótka odpowiedź: tak

Trzeba być nieco bardziej ostrożnym, stawiając pytanie. Myśląc o obwodzie złożonym z przygotowania stanu, jednostek i pomiarów, w zasadzie zawsze możliwe jest „ukrycie” wszystkiego, co chcemy, na przykład operacji oplątujących, wewnątrz pomiaru. Bądźmy więc precyzyjni. Chcemy zacząć od rozłącznego stanu wielu kubitów, a końcowe pomiary powinny składać się z pomiarów pojedynczych kubitów. Czy obliczenia muszą przechodzić przez stan splątany w którymś momencie obliczeń?

Czyste stany

Przyjmijmy jeszcze jedno założenie, że stan początkowy jest stanem czystym (produktowym). W takim przypadku system musi przejść w stan zaplątany. Jeśli tak się nie stanie, łatwo przeprowadzić symulację obliczeń na klasycznym komputerze, ponieważ wszystko, co musisz zrobić, to zachować w pamięci pojedynczych stanów czystych kubitów i aktualizować je pojedynczo w trakcie obliczeń. $n$

Można nawet zapytać, ile splątania jest konieczne. Znów istnieje wiele różnych sposobów, w jakie splątanie można przenosić w różnych momentach. Dobrym modelem, który zapewnia dość uczciwą miarę splątania, jest obliczenie kwantowe oparte na pomiarach . Tutaj przygotowujemy początkowy stan zasobów, a pomiary pojedynczego kubitu definiują obliczenia, które mają miejsce. To pozwala nam zapytać o uwikłanie stanu zasobu. Musi istnieć splątanie i, w pewnym sensie, musi być co najmniej „dwuwymiarowe”, nie może to być splątanie generowane między najbliższymi sąsiadami systemu na linii [ref] . Co więcej, można pokazać, że większość stanów kubitów jest zbyt splątanych $n$ aby umożliwić obliczenia w ten sposób.

Stany mieszane

Zastrzeżeniem we wszystkim, co powiedziałem do tej pory, jest to, że mówimy o czystych stanach. Na przykład możemy łatwo symulować nieplączące się obliczenia stanów czystego produktu. Ale co z mieszanymi stanami? Stan mieszany można rozdzielić, jeśli można go zapisać w postaci Co ważne, nie ma limitu wartości , liczby wyrażeń w sumie. Jeśli liczba wyrażeń w sumie jest niewielka, to na podstawie poprzedniego argumentu możemy symulować działanie obwodu nieplączącego się. Ale jeśli liczba terminów jest duża, to (o ile wiem) pozostaje otwarte pytanie, czy można to klasycznie zasymulować, czy też może to dać ulepszone obliczenia.

ρ = \sum_{i = 1}^{N} p_{i} ρ_{i}^{(1)} \otimes ρ_{i}^{(2)} \otimes \dots \otimes ρ_{i}^{(n)} .

$\rho=\sum_{i=1}^Np_i\rho^{(1)}_i\otimes\rho^{(2)}_i\otimes\ldots\otimes\rho^{(n)}_i.$

N

$N$

— DaftWullie
źródło

Ta praca ( arxiv.org/pdf/quant-ph/0301063.pdf ) może być tutaj interesująca. Splątanie w układzie kwantowym musi być skalowane jako wielomian wielkości układu, aby uzyskać wykładnicze przyspieszenie kwantowe. Algorytm kwantowy można klasycznie zasymulować za pomocą zasobów skalowanych jak wykładniczy splątanie.

— biryani

chociaż nie-wykładnicze przyspieszenia, takie jak Grover, potrafią uciec z niewielką ilością splątania, moja własna praca .

— DaftWullie

Co sądzisz o tym artykule ? Nie miałem czasu, aby dokładnie to przemyśleć, ale stwierdza, że Grovera można wykonać bez uwikłania (przy niższych prędkościach).

— Steven Sagona

@StevenSagona To rodzaj oszustwa / sprzedaży. Chociaż zwykle mówimy o kubitach, z przestrzenią Hilberta o wymiarze , możesz uzyskać tę przestrzeń Hilberta, używając pojedynczej cząstki o przestrzeni Hilberta o wymiarze (np. Wysyłając cząstkę w dół różnymi ścieżkami) i na pewno nie ma żadnego splątania (w rzeczywistości istnieje filozoficzne pytanie dotyczące superpozycji / splątania na podstawie ścieżki). Z tą konwersją wiążą się koszty wejścia, ale przy użyciu modelu wyroczni, podobnie jak w przypadku Grovera, koszty te zostają ukryte i wydaje się, że osiąga to samo.

n

$n$

2^{n}

$2^n$

2^{n}

$2^n$

2^{n}

$2^n$

— DaftWullie

O, rozumiem. Dzięki za odpowiedź, to faktycznie rozwiązuje niektóre konceptualne pytania w mojej głowie (ponieważ nie było dla mnie oczywiste, dlaczego zwykła superpozycja jednej cząstki jest niewystarczająca do zapewnienia takich samych mechanizmów jak te splątane układy).

— Steven Sagona

Czy splątanie jest konieczne do obliczeń kwantowych?

Czyste stany

Stany mieszane