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?
cc.complexity-theory
quantum-computing
circuit-complexity
Bill GASARCH
źródło
źródło
Odpowiedzi:
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 0 jest zwykle definiowany jako posiadający nieograniczone bramy fanowskie Toffoli i bramy jednububitowe. QAC 0 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 0 i TC 0 .
Tak więc oczywistym pytaniem, które należy zadać, jest to, czy PARITY jest zawarte w QAC 0 , i jest to otwarty problem. Jest to równoważne z pytaniem, czy QAC 0 = QAC 0 wf . Wydaje mi się, że wierzy się, że PARITY nie ma QAC 0 . Więcej informacji można znaleźć w ankiecie Obwody kwantowe o małej głębokości autorstwa Bera, Green i Homer.
źródło
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.
źródło