Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification

While quantum speed-up in solving certain decision problems by a fault-tolerant universal quantum computer has been promised, a timely research interest includes how far one can reduce the resource requirement to demonstrate a provable advantage in quantum devices without demanding quantum error correction, which is crucial for prolonging the coherence time of qubits. We propose a model device made of locally interacting multiple qubits, designed such that simultaneous single-qubit measurements on it can output probability distributions whose average-case sampling is classically intractable, under similar assumptions as the sampling of noninteracting bosons and instantaneous quantum circuits. Notably, in contrast to these previous unitary-based realizations, our measurement-based implementation has two distinctive features. (i) Our implementation involves no adaptation of measurement bases, leading output probability distributions to be generated in constant time, independent of the system size. Thus, it could be implemented in principle without quantum error correction. (ii) Verifying the classical intractability of our sampling is done by changing the Pauli measurement bases only at certain output qubits. Our usage of random commuting quantum circuits in place of computationally universal circuits allows a unique unification of sampling and verification, so they require the same physical resource requirements in contrast to the more demanding verification protocols seen elsewhere in the literature.

Figure 1

The MQC gadgets utilized in our protocol. We describe the formation circuit and outcome-dependent logical operations for each when sites are measured everywhere in some single-qubit Pauli basis. Initial states on input sites (dotted) are teleported to output sites (green online or gray in print grayscale) and acted on by characteristic logical operations and measurement-dependent random byproduct operators. These outputs are identified with the inputs of future gadgets. The relationship between the formation circuits shown and the logical operations implemented is given by contracting with the appropriate measurement outcomes, which additionally contributes a scalar factor of $\frac{1}{\sqrt{2}}$ per measurement (not shown). Mathematically, this leads our measurement outcomes $s_i$ to occur uniformly randomly. (a) One-dimensional cluster state wire of length 2, where solid lines indicate cz formation unitaries. Measuring $X$ on two sites implements the identity, with a uniformly random Pauli byproduct group. (b) Planar MQC gadget for implementing nonplanar wire crossings. Measuring $X$ on six sites implements swap, with a byproduct group of uniformly random two-qubit Pauli operators. (c) Non-Clifford gadget for conditional ccz, where triangles indicate ccz gates used to form the gadget. Measuring $Y$ on three nonlogical control sites (dark red smaller circles) gives ccz on sites $A$, $B$, and $C$, whereas measuring $Z$ on these sites instead gives the identity. In both cases, the teleportation is trivial (output and input sites coincide), while the byproduct group is a product of uniformly random cz gates between $A$ and $C$ and between $B$ and $C$.

Figure 2

Overview of our constant-time MQC protocol for implementing the unitary $U_f=U_{\mathbf{b}+\mathbf{c}}{U}_{\mathbf{a}}$ which prepares the sampling state $|{\psi }_f\rangle$. Our intended logical operation is $U_{\mathbf{a}}$, while $U_{\mathbf{b}+\mathbf{c}}$ is a byproduct contribution containing uniformly random $\mathbf{b}$ and $\mathbf{c}$. (a) Circuit diagram for $U_{\mathbf{a}}$, which is formed from several repeating loops. In loop I, qubits $i_0$ and $j_0$ remain fixed and all qubits $k>i_0,j_0$ are sequentially cycled past $i_0$ and $j_0$ and acted on by a conditional three-body gate ${\left({\text{CCZ}}_{i_0{j}_{0}k}\right)}^{a_{i_0{j}_{0}k}}$ depending on the binary coefficient $a_{i_0{j}_{0}k}$ in $f$. The order of these qubits is reversed after loop I, which is undone by a sequence of swap gates with circuit depth $O\left(n\right)$. Loop II then involves replacing qubit $j_0$ by $j_0+1$ and repeating loop I for all triples $(i_0,j_0+1,k)$, where $k>i_0,j_0+1$. Loop II continues cycling qubit $j$ and applying loop I until all triples $(i_0,j,k)$ have been addressed. Loop III (not shown) then involves replacing qubit $i_0$ by $i_0+1$ and repeating loop II for all triples $(i_0+1,j,k)$. At the completion of loop III, we have addressed all triples of qubits within circuit depth $O\left(n^3\right)$, producing the output state $|{\psi }_{\mathbf{a}}\rangle$. (b) Concrete example of how the above protocol is implemented in MQC using our resource state $|{\mathrm{\Psi }}_{\mathrm{prep}}\rangle$, for $n=4$. One-dimensional cluster state wires let us teleport information between non-Clifford gadgets, which apply the logical gate ${\left(\text{CCZ}\right)}^{a_{ijk}}$ via an $a_{ijk}$-dependent choice of $Y$ or $Z$ measurement on control sites (dark red smaller circles). While our state is drawn with nonplanar wire crossings, these are simulated using the planar swap gadgets in Fig. 1. Measuring all preparation sites simultaneously prepares a random $n$-qubit state $|{\psi }_f\rangle$ on the output sites (circles on the right, green online or gray in print grayscale), where $f=\mathbf{a}+\mathbf{b}+\mathbf{c}$ contains a deterministic $\mathbf{a}$ set by the measurement bases and a uniformly random $\mathbf{b}+\mathbf{c}$ arising from random byproduct operators. The final $n$-qubit measurement is chosen to randomly implement sampling via all $X$ measurements or verification via a mixture of $X$ and $Z$ measurements.