Czy PARITY w QAC_0 (jeśli to ma sens)

Jak dobrze wiadomo PARITY nie może być wykonane w obwodach o stałej wielkości o wielkiej wielkości, aw rzeczywistości obwody stałe wymagają liczby EXP bramek.

Co z obwodami QUANTUM?

a) Czy PARITY można wykonać za pomocą obwodu kwantowego, który ma stałą głębokość i liczbę bramek?

b) Czy moje pytanie ma w ogóle sens?

Pytanie ma sens, a krótka odpowiedź brzmi: to otwarty problem.

Oto długa odpowiedź: w zależności od tego, jak zdefiniujesz nieograniczone obwody kwantowe o stałej głębokości, możesz uzyskać różne klasy. QAC ⁰ jest zwykle definiowany jako posiadający nieograniczone bramy fanowskie Toffoli i bramy jednububitowe. QAC ⁰ _wf to klasa, w której zezwalamy również na bramkę typu „fanout”, która kopiuje bit wejściowy na wiele wyjść. (Implementuje | a> | 0> ... | 0> -> | a> | a> ... | a>). Ta klasa jest naprawdę potężna, ponieważ oprócz PARITY i AC ^{0 zawiera} także ACC ⁰ i TC ⁰ .

Tak więc oczywistym pytaniem, które należy zadać, jest to, czy PARITY jest zawarte w QAC ⁰ , i jest to otwarty problem. Jest to równoważne z pytaniem, czy QAC ⁰ = QAC ⁰ _wf . Wydaje mi się, że wierzy się, że PARITY nie ma QAC ⁰ . Więcej informacji można znaleźć w ankiecie Obwody kwantowe o małej głębokości autorstwa Bera, Green i Homer.

Co zaskakujące, liczba dodatkowych kubitów pracy (ancilla) ma znaczenie. W tej chwili wiadomo, że PARITY nie znajduje się w QAC_0 z ograniczonymi szeregami. Kwantowe dolne granice dla fanouta dają jeden dowód na obwody wykorzystujące co najwyżej liniowo wiele ancilla, a doi: 10.1016 / j.ipl.2011.05.002 daje kolejny dowód na obwody bez żadnych dodatków.