Tymczasowo płaskie jednokierunkowe obliczenia kwantowe

Na sercu jestem fizykiem, więc myślę, że One-Way Quantum Computing jest genialny. W szczególności obliczenia kwantowe oparte na pomiarach stanu graficznego (MBQC) stanowiły bardzo udany rozwój badań nad obliczeniami kwantowymi, których autorami są Raussendorf & Briegel . Trzeba tylko przygotować stan splątania wieloczęściowego zgodnie z opisem na wykresie, a następnie wykonać kolejne pomiary na każdym węźle lub kubicie (pomiary adaptacyjne dla obliczeń deterministycznych).

Innym doskonałym aspektem tego podejścia jest to, że obwody Clifforda można wdrożyć w pojedynczej rundzie pomiarów, jak pokazują Raussendorf, Browne i Briegel . Obwody te mogą być klasycznie symulowane (efektywnie), jak pokazują Gottesman i Knill, więc jest to interesujące połączenie między klasyczną symulacją a zasobami czasowymi.

Jednak nie wszystkie tymczasowo płaskie obwody stanu wykresu MBQC (składające się z jednej rundy pomiarów) są uważane za klasycznie możliwe do symulacji. Na przykład rodziny obwodów w modelu obwodu kwantowego składającym się z bramek dojazdowych zwanych obwodami IQP wprowadzonymi przez Shepherda i Bremnera można zaimplementować w jednym kroku czasowym w MBQC. Uważa się, że te obwody IQP nie są klasycznie symulowalne (w kategoriach złożoności obliczeniowej doprowadziłoby to do upadku hierarchii wielomianowej) .

Zobacz także ładny opis klasy obwodów zaimplementowanych w jednym kroku czasowym tutaj . Biorąc pod uwagę, że jednostki dojeżdżające do pracy / diagonalne mogą mieć pewne interesujące zachowanie, ale obwody nie dojeżdżające do pracy są klasycznie symulowalne. Byłoby interesujące, gdyby istniały obwody nie dojeżdżające do pracy, które można wdrożyć, ale jeszcze nie wykazano, że są klasycznie symulowalne.

W każdym razie moje pytanie brzmi:

Czy istnieją inne interesujące obwody, które można zaimplementować w jednym kroku czasowym w MBQC?

Chociaż wolałbym relacje od złożoności obliczeniowej lub klasycznej symulacji, znalazłem coś interesującego.

Edycja: Po doskonałej odpowiedzi Joe poniżej, powinienem wyjaśnić kilka rzeczy. Jak powiedział Joe (i nieco zawstydzająco powiedziałem w jednym z moich własnych artykułów), pojedyncze okrągłe obwody MBQC są w IQP. Mówiąc ściślej, interesują mnie interesujące obwody w problemach IQP, które można zaimplementować w jednej rundzie pomiarów w MBQC. Ciekawym przykładem są obwody Clifford. Jeśli istnieją inne przykłady, które są klasycznie symulowalne, byłoby to niezwykle interesujące. Ponieważ uważa się, że symulacja obwodów IQP jest mało prawdopodobna klasycznie, interesujące byłoby znalezienie instancji takich obwodów.

Biorąc pod uwagę aktualizację tego pytania, pomyślałem, że najlepiej jest opublikować to jako nową odpowiedź, ponieważ jest to całkowicie odmienne od mojej poprzedniej odpowiedzi i mam nadzieję, że jest interesujące.

$n$

$j$$X$$Z$$\exp{\big(i \theta \prod_i Z_i \big)}$$i$$j$$j$$|0\rangle\langle 0|\otimes I + |1\rangle\langle 1|\otimes \prod_i Z_i$$|+\rangle$$\frac{1}{\sqrt{2}}\left(|0\rangle \otimes I + |1\rangle\otimes \prod_i Z_i\right)$$\exp(i\theta X)$$\frac{1}{\sqrt{2}}\left(|0\rangle \otimes (\cos \theta I + i \sin \prod_i Z_i) + |1\rangle\otimes (\prod_i Z_i\right)(\cos \theta I + i \sin \prod_i Z_i)$. Thus up to a Pauli correction of $\prod_i Z_i$ we deterministically implement the operator $\cos \theta I + i \sin \prod_i Z_i$ which is just an alternate form of $\exp{\big(i \theta \prod_i Z_i \big)}$.

Note that such operators are the Hadamard transform of the basic building blocks of X-programs, and that all such operators commute independent of which qubits they operate on. IQP is defined in terms of X-programs which are restricted to having a number of terms at most polynomial in the number of qubits. However, there are an exponential number of independent such terms, and so it is possible to specify temporally flat computations which have exponential sized X-programs. Indeed the $n$-input phase Toffoli gate (i.e. the $C....CZ$ gate) is an example of such an operation that requires an exponential number of commuting gates, though it can be achieved with a linear number of non-commuting gates. Thus it is possible to construct single layer measurement based computations which implement X-programs which are exponential in the number of logical qubits, and hence outside of IQP for the logical qubits (though inside IQP for the physical qubits).

Potentially there is a problem here, in that they require an exponential number of parameters to uniquely specify all of the pairs in the X-program. However, if you consider such angles to be generated algorithmically (say with the restriction that each angle can be computed in polynomial time) then it is not even clear whether simulating such a computation can be done in BQP.

It doesn't make sense to me to ask about non-commuting operators being implemented in a single time step (though constant depth certainly makes sense). However, you can implement non-commuting gates on the logical subspace of an MBQC which are implemented using commuting measurements on the resource state, though the implemented gates are not deterministic.

Actually, I believe you are viewing IQP more narrowly than you probably should. The answer to your question is that any MBQC which can be implemented in a single measurement layer in MBQC is contained in IQP. This is simply because rather than expressing the result in terms of the logical Hilbert space, you can express it as a series of commuting operations on the physical qubits. Shepherd and Bremner actually deal with this in their paper (in section 5.2 where such operations are called graph-programs).