Czy BQP to tylko czas? Czy to ma sens?

Wydaje się, że klasa złożoności BQP (kwantowy wielomian czasowy z ograniczonym błędem) jest zdefiniowana tylko biorąc pod uwagę czynnik czasu. Czy to zawsze ma znaczenie? Czy istnieją algorytmy, w których obliczeniowy czas skaluje się wielomianowo z rozmiarem wejściowym, ale inne zasoby, takie jak pamięć skalowane wykładniczo?

BQP jest definiowany z uwzględnieniem wielkości obwodu , czyli całkowitej liczby bramek. Oznacza to, że obejmuje:

• Liczba kubitów - ponieważ możemy zignorować kubity, na które nie działa brama. Będzie to ograniczone wielomianowo względem wielkości wejściowej, a często skromnego wielomianu (np. Algorytm Shora obejmuje tylko pewną liczbę kubitów, która jest stałym współczynnikiem razy wielkość wejściowa).
• Głębokość obwodu (lub „czas”) - ponieważ najdłuższy czas obliczeń może zająć to wykonanie jednej bramki po drugiej, bez wykonywania żadnych operacji równolegle.
• Komunikacja z systemami sterowania - ponieważ wykonywane bramki są pobierane z jakiegoś skończonego zestawu bramek, a nawet jeśli zezwalamy na pomiary pośrednie, ilość komunikacji wymagana do wskazania wyniku pomiaru i ilość obliczeń wymaganych do ustalenia, co zostanie zrobione dalej jest zwykle stałą dla każdej operacji.
• Interakcje między układami kwantowymi - nawet jeśli weźmiemy pod uwagę architekturę, która nie ma interakcji typu „wszystko dla wszystkich” lub coś podobnego, możemy symulować taką łączność, wykonując jawne operacje SWAP, które same mogą zostać rozłożone na stałą liczbę dwóch operacje qubit. Może to dać nam zauważalny narzut wielomianowy, który wpływa na praktyczność algorytmu dla danej architektury, ale nie ukrywa wykładniczej ilości pracy.
• Energia - ponownie, ponieważ obwody są rozkładane na skończony zestaw bramek, nie ma oczywistego sposobu na uzyskanie pozornego przyspieszenia poprzez „szybsze wykonywanie bram” lub ukrywanie pracy w egzotycznej interakcji, jeśli nasze granice dotyczą liczba operacji wykonanych z dość podstawowego zestawu operacji. Ta uwaga jest ważniejsza w adiabatycznym obliczeniu kwantowym: nie możemy próbować uniknąć małych luk, wzmacniając cały krajobraz energetyczny tak bardzo, jak nam się podoba - co oznacza, że ​​zamiast tego musimy poświęcić więcej czasu na obliczenia, co odpowiada obrazowi obwodu obwód z większą ilością bramek.

W efekcie liczenie liczby bramek ze stałej wielkości pozwala uchwycić wiele rzeczy, o które możesz się martwić jako praktyczne zasoby: pozostawia niewiele miejsca na ukrycie wszystkiego, co jest potajemnie bardzo drogie.

Przynajmniej nie do pamięci, ponieważ każdy dostęp do pamięci wymaga $O(1)$ 'czas'.

W zakresie złożoności czasu „czas” jest nieco mylący, ponieważ w rzeczywistości liczymy liczbę podstawowych operacji wymaganych do wykonania algorytmu. Przy dodatkowym założeniu, że operacje te można wykonać w „$O(1)$czas ”, możemy powiedzieć, że nasz algorytm ma„ złożoność czasową ”. Ale tak naprawdę mamy na myśli to, że mamy „złożoność operacji”, którą wyrażamy w czasie.

Myślę, że wyraźniej jest, że liczenie operacji elementarnych jest podstawową i ważną miarą liczby zasobów wymaganych przez algorytm, ponieważ zawsze możemy zdecydować, ile zasobów potrzebuje każda operacja elementarna.

Podczas gdy w definicji BQP i dla algorytmów kwantowych rozważamy złożoność obwodów zamiast „złożoności operacji”, złożoność obwodów można ponownie zdefiniować w kategoriach operacji na maszynach Turinga, więc obowiązuje to samo rozumowanie.