Złożoność optymalizacji w stosunku do grupy jednolitej

Jaka jest złożoność obliczeniowa optymalizacji różnych funkcji w grupie jednolitej ? $\mathcal{U}(n)$

Typowe zadanie, często wynikające z teorii informacji kwantowej byłoby maksymalizując ilość typu (lub wyższych wielomiany rzędu w ) w stosunku do wszystkich macierze jednostkowe . Czy tego rodzaju optymalizacja jest wydajna (być może w przybliżeniu) do obliczenia, czy też jest trudna do przeprowadzenia? (być może jest to dobrze znane, ale nie mogłem znaleźć żadnych ogólnych odniesień) $\mathrm{Tr}AUBU^{\dagger}$ $U$ $U$

— Marcin Kotowski
źródło

czy możesz ograniczyć „różne funkcje” do „wielomianów nad jednostkami”?

— Artem Kaznatcheev

Nie wiem wiele o tym, jak powstają te problemy, ale jaki byłby naturalny klasyczny analog tego problemu? Czy znasz złożoność tego problemu?

— Robin Kothari

Jest bardzo fajny artykuł Rogera Brocketta z 1991 roku, który pokazuje, jak wyrazić sortowanie i programowanie liniowe w zasadniczo opisanej przez ciebie formie, ale w matrycach ortogonalnych. Brak wzmianki o złożoności, ale fakt, że dwa bardzo różne problemy można wyrazić w ten sam sposób, oznacza, że musisz wiedzieć coś o strukturze problemu, aby dokonać oceny złożoności: eecs.berkeley.edu/~sburden/research/ jonathan / Brockett1991.pdf

— Suresh Venkat

@Artem: tak, myślę, że w praktyce wielomianami niskich stopni są najbardziej odpowiednie.

— Marcin Kotowski

Sprowadza się to do rozkładu własnego

w podanym przez ciebie przykładzie stopnia 2. W przypadku pustelnika

, jednostkowy

może być użyty do maksymalizacji śladu poprzez wyrównanie przestrzeni własnych

z tymi z

; wystarczy zatem zmaksymalizować iloczyn iloczynu sekwencji ich wartości własnych, co jest trywialne, jeśli

są dodatnie w połowie skończone (i przypadek, do którego możemy zmniejszyć, dodając wielokrotności tożsamości do przeskalowania wartości własnych). A może interesują Cię znacznie bardziej ogólne przypadki, niekoniecznie motywowane mechaniką kwantową w układach małowymiarowych?

A

$A$

B

$B$

A

$A$

B

$B$

U

$U$

U B U^{†}

$U B U^\dagger$

A

$A$

A

$A$

B

$B$

— Niel de Beaudrap

Odpowiedzi:

Przepraszam za spóźnienie! W teorii obliczeń kwantowych istnieje wiele przykładów problemów związanych z optymalizacją w obrębie grupy jednolitej, które, co zaskakujące (przynajmniej dla mnie), można rozwiązać w (klasycznym) czasie wielomianowym przez redukcję do programowania półfinałowego.

Oto wczesny przykład: rozwiązanie mojego problemu z 2000 r., W 2003 r. Barnum, Saks i Szegedy wykazały, że Q (f), kwantowa złożoność kwerendy funkcji boolowskiej f: {0,1} ⁿ → {0,1 }, można obliczyć w funkcji wielomianu czasowego w 2 ⁿ (tj. wielkości tabeli prawdy f). Myślałam o tym, ale nie wiedziałam, jak to zrobić, ponieważ trzeba zoptymalizować prawdopodobieństwo sukcesu we wszystkich możliwych algorytmach kwantowych zapytań, każdy z własnym zestawem (prawdopodobnie 2 ^n- wielkości) jednolitych macierzy. Barnum i in. zredukowany do SDP poprzez wykorzystanie „dualności” między matrycami jednolitymi a dodatnimi macierzami półfinałowymi, tzw. izomorfizm Choi-Jamiolkowskiego. Bardziej aktualny i prostszy SDP charakteryzujący Q (f), patrz artykuł Reichardta z 2010 r. Pokazujący, że metoda przeciwnika o wadze ujemnej jest optymalna.

Innym ważnym przypadkiem wykorzystania tej sztuczki są kwantowe interaktywne systemy próbne. Chociaż nie jest to intuicyjnie oczywiste, w 2000 Kitaev i Watrous udowodnili, że QIP ⊆ EXP. zmniejszając problem optymalizacji w stosunku do macierzy jednolitych wielkości wykładniczej, które powstają w 3-okrągłym kwantowym interaktywnym systemie dowodu, do rozwiązania SDP wielkości pojedynczej wykładniczej (znowu, jak sądzę, stosując izomorfizm Choi-Jamiolkowskiego między stanami mieszanymi i macierze jednolite). Ostatni przełom QIP = PSPACE wynikał z pokazania, że ten konkretny SDP można w przybliżeniu rozwiązać jeszcze lepiej, w NC (tj. Za pomocą obwodów o głębokości logarytmicznej).

Tak więc, bez względu na konkretny problem optymalizacji dotyczący grupy jednolitej, domyślam się, że można go rozwiązać szybciej niż myślisz - jeśli nie w jeszcze prostszy sposób, to przez redukcję do SDP!

— Scott Aaronson
źródło

Drogi Scott! Barnum, Saks i Szegedy nie wspominają wprost o izomorfizmie Choi-Jamiołkowskiego i nie rozumiem, w jaki sposób jest to związane z ich budową. Czy mógłbyś rozwinąć tę kwestię? Pytam, ponieważ próbuję zrozumieć, czy podobny wynik jest możliwy w przypadku wadliwych wyroczni.

— Joris,

-3

Ustalenie, czy dwie macierze Hadamarda są równoważne, stanowi całkowity problem z Graph Isomorphism (GI). Brendon McKay ma artykuł na ten temat. Patrz BD McKay, równoważność Hadamarda za pomocą izomorfizmu grafowego, Discrete Mathematics, 27 (1979) 213-216.

— Dursun
źródło

nie tak mówi gazeta. artykuł dotyczy „równoważności hadamarda”

\pm 1

$\pm 1$ matryce

— Sasho Nikolov