Measurement-based quantum computation (MBQC) is a strong contender for realizing quantum computers. A critical question for MBQC is the identification of resource graph states that can enable universal quantum computation. Any such universal family must have unbounded entanglement width, which is equivalent to the ability to produce any circle graph state from the states in the family using only local Clifford operations, local Pauli measurements, and classical communication. Yet, it was not previously known whether or not circle graph states themselves are a universal resource. We show that, in spite of their expressivity, circle graph states are not efficiently universal for MBQC (i.e., assuming $\mathsf{BQP} \neq \mathsf{BPP}$). We prove this by articulating a precise graph-theoretic correspondence between circle graph states and a certain subset of fermionic Gaussian states. This is accomplished by synthesizing a variety of techniques that allow us to handle both stabilizer states and fermionic Gaussian states at the same time. As such, we anticipate that our developments may have broader applications beyond the domain of MBQC as well.
Measurement-based quantum computation (MBQC) is a strong contender for realizing quantum computers. A critical question for MBQC is the identification of resource graph states that can enable universal quantum computation. Any such universal family must have unbounded entanglement width, which is equivalent to the ability to produce any circle graph state from the states in the family using only local Clifford operations, local Pauli measurements, and classical communication. Yet, it was not previously known whether or not circle graph states themselves are a universal resource. We show that, in spite of their expressivity, circle graph states are not efficiently universal for MBQC (i.e., assuming BQP=BPP). We prove this by articulating a precise graph-theoretic correspondence between circle graph states and a certain subset of fermionic Gaussian states. This is accomplished by synthesizing a variety of techniques that allow us to handle both stabilizer states and fermionic Gaussian states at the same time. As such, we anticipate that our developments may have broader applications beyond the domain of MBQC as well.
Circle graph states are a structurally important family of graph states. The family's entanglement is a priori high enough to allow for universal measurement-based quantum computation (MBQC); however, MBQC on circle graph states is actually efficiently classically simulable. In this work, we paint a detailed picture of the local equivalence of circle graph states. First, we consider the class of all graph states that are local unitary (LU)-equivalent to circle graph states. In graph-theoretical terms, this LU-equivalence class is the set of all graphs reachable from the family of circle graphs by applying r-local complementations. We prove that the only graph states that are LU-equivalent to circle graph states are circle graph states themselves: circle graphs are closed under r-local complementation. Second, we show that bipartite circle graph states, i.e., 2-colorable circle graph states, are in one-to-one correspondence with planar code states, on which MBQC is known to be efficiently classically simulable. Leveraging this correspondence, we present alternative, simple proofs that (1) if a planar code state is LU-equivalent to a stabilizer state, they are in fact local Clifford (LC)-equivalent to it and that (2) MBQC on all circle graph states is efficiently classically simulable. Third and finally, we demonstrate that the problem of counting the number of graph states LU-equivalent to a given graph state is #P-hard.
We introduce a new family of models for measurement-based quantum computation which are deterministic and approximately universal. The resource states which play the role of graph states are prepared via 2-qubit gates of the form exp(−iπ2nZ⊗Z) . When n=2 , these are equivalent, up to local Clifford unitaries, to graph states. However, when n>2 , their behaviour diverges in two important ways. First, multiple applications of the entangling gate to a single pair of qubits produces non-trivial entanglement, and hence multiple parallel edges between nodes play an important role in these generalised graph states. Second, such a state can be used to realise deterministic, approximately universal computation using only Pauli Z and X measurements and feed-forward. Even though, for n>2 , the relevant resource states are no longer stabiliser states, they admit a straightforward, graphical representation using the ZX-calculus. Using this representation, we are able to provide a simple, graphical proof of universality. We furthermore show that for every n>2 this family is capable of producing all Clifford gates and all diagonal gates in the n -th level of the Clifford hierarchy.
We introduce a new family of models for measurement-based quantum computation which are deterministic and approximately universal. The resource states which play the role of graph states are prepared via 2-qubit gates of the form exp(−i2nπZ⊗Z). When n=2, these are equivalent, up to local Clifford unitaries, to graph states. However, when n>2, their behaviour diverges in two important ways. First, multiple applications of the entangling gate to a single pair of qubits produces non-trivial entanglement, and hence multiple parallel edges between nodes play an important role in these generalised graph states. Second, such a state can be used to realise deterministic, approximately universal computation using only Pauli Z and X measurements and feed-forward. Even though, for n>2, the relevant resource states are no longer stabiliser states, they admit a straightforward, graphical representation using the ZX-calculus. Using this representation, we are able to provide a simple, graphical proof of universality. We furthermore show that for every n>2 this family is capable of producing all Clifford gates and all diagonal gates in the n-th level of the Clifford hierarchy.
In this paper, we build a framework allowing for a systematic investigation of the fundamental issue: ' Which quantum states serve as universal resources for measurement-based (one-way) quantum computation? ' We start our study by re-examining what is exactly meant by 'universality' in quantum computation, and what the implications are for universal one-way quantum computation. Given the framework of a measurement-based quantum computer, where quantum information is processed by local operations only, we find that the most general universal one-way quantum computer is one which is capable of accepting arbitrary classical inputs and producing arbitrary quantum outputs—we refer to this property as CQ-universality. We then show that a systematic study of CQ-universality in one-way quantum computation is possible by identifying entanglement features that are required to be present in every universal resource. In particular, we find that a large class of entanglement measures must reach its supremum on every universal resource. These insights are used to identify several families of states as being not universal, such as one-dimensional (1D) cluster states, Greenberger–Horne–Zeilinger (GHZ) states, W states, and ground states of non-critical 1D spin systems. Our criteria are strengthened by considering the efficiency of a quantum computation, and we find that entanglement measures must obey a certain scaling law with the system size for all efficient universal resources. This again leads to examples of non-universal resources, such as, e.g. ground states of critical 1D spin systems. On the other hand, we provide several examples of efficient universal resources, namely graph states corresponding to hexagonal, triangular and Kagome lattices. Finally, we consider the more general notion of encoded CQ-universality, where quantum outputs are allowed to be produced in an encoded form. Again we provide entanglement-based criteria for encoded universality. Moreover, we present a general procedure to construct encoded universal resources.
We investigate which entanglement resources allow universal measurement-based quantum computation via single-qubit operations. We find that any entanglement feature exhibited by the 2D cluster state must also be present in any other universal resource. We obtain a powerful criterion to assess the universality of graph states by introducing an entanglement measure which necessarily grows unboundedly with the system size for all universal resource states. Furthermore, we prove that graph states associated with 2D lattices such as the hexagonal and triangular lattice are universal, and obtain the first example of a universal nongraph state.
Fermions, as a major class of quantum particles, provide platforms for quantum information processing beyond the possibilities of spins or bosons, which have been studied more extensively. One particularly interesting model to study, in view of recent progress in manipulating ultracold fermion gases, is the fermionic version of measurement-based quantum computation (MBQC), which implements full quantum computation with only single-site measurements on a proper fermionic many-body resource state. However, it is not known which fermionic states can be used as the resource states for MBQC and how to find them. In this paper, we generalize the framework of spin MBQC to fermions. In particular, we provide a general formalism to construct many-body entangled fermion resource states for MBQC based on the fermionic projected entangled pair state representation. We give a specific fermionic state which enables universal MBQC and demonstrate that the nonlocality inherent in fermion systems can be properly taken care of with suitable measurement schemes. Such a framework opens up possibilities of finding MBQC resource states which can be more readily realized in the laboratory.