There are two types of universality in measurement-based quantum computation (MBQC): strict and computational. It is well known that the former is stronger than the latter. We present a method of transforming from a certain type of computationally universal MBQC to a strictly universal one. Our method simply replaces a single qubit in a resource state with a Pauli-Y eigenstate. We applied our method to show that hypergraph states can be made strictly universal with only Pauli measurements, while only computationally universal hypergraph states were known.
There are two types of universality in measurement-based quantum computation (MBQC): strict and computational. It is well known that the former is stronger than the latter. We present a method of transforming from a certain type of computationally universal MBQC to a strictly universal one. Our method simply replaces a single qubit in a resource state with a Pauli-Y eigenstate. We applied our method to show that hypergraph states can be made strictly universal with only Pauli measurements, while only computationally universal hypergraph states were known.
Measurement-based quantum computing is one of the most promising quantum computing models. Although various universal resource states have been proposed so far, it was open whether only two Pauli bases are enough for both of universal measurement-based quantum computing and its verification. In this paper, we construct a universal hypergraph state that only requires X and Z-basis measurements for universal measurement-based quantum computing. We also show that universal measurement-based quantum computing on our hypergraph state can be verified in polynomial time using only X and Z-basis measurements. Furthermore, in order to demonstrate an advantage of our hypergraph state, we construct a verifiable blind quantum computing protocol that requires only X and Z-basis measurements for the client.
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.
Complex entangled states are the key resources for measurement-based quantum computations, which is realised by performing a sequence of measurements on initially entangled qubits. Executable quantum algorithms in the graph-state quantum computing model are determined by the entanglement structure and the connectivity of entangled qubits. By generalisation from graph-type entanglement in which only the nearest qubits interact to a new type of hypergraph entanglement in which any subset of qubits can be arbitrarily entangled via hyperedges, hypergraph states represent more general resource states that allow arbitrary quantum computation with Pauli universality. Here we report experimental preparation, certification and processing of complete categories of four-qubit hypergraph states under the principle of local unitary equivalence, on a fully reprogrammable silicon-photonic quantum chip. Genuine multipartite entanglement for hypergraph states is certificated by the characterisation of entanglement witness, and the observation of violations of Mermin inequalities without any closure of distance or detection loopholes. A basic measurement-based protocol and an efficient resource state verification by color-encoding stabilizers are implemented with local Pauli measurement to benchmark the building blocks for hypergraph-state quantum computation. Our work prototypes hypergraph entanglement as a general resource for quantum information processing.
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.
Hypergraph states are generalizations of graph states where controlled-Z gates on edges are replaced with generalized controlled-Z gates on hyperedges. Hypergraph states have several advantages over graph states. For example, certain hypergraph states, such as the Union Jack states, are universal resource states for measurement-based quantum computing with only Pauli measurements, while graph state measurement-based quantum computing needs non-Clifford basis measurements. Furthermore, it is impossible to classically efficiently sample measurement results on hypergraph states unless the polynomial hierarchy collapses to the third level. Although several protocols have been proposed to verify graph states with only sequential single-qubit Pauli measurements, there was no verification method for hypergraph states. In this paper, we propose a method for verifying a certain class of hypergraph states with only sequential single-qubit Pauli measurements. Importantly, no i.i.d. property of samples is assumed in our protocol: any artificial entanglement among samples cannot fool the verifier. As applications of our protocol, we consider verified blind quantum computing with hypergraph states, and quantum computational supremacy demonstrations with hypergraph states.
Any computational process is built from a sequence of components. In this context, there are at least two ways in which “component” can be interpreted: physically and logically. The former can be understood as referring to the hardware for the computation, i.e., the physical substrate where the computation “takes place”, while the latter can be understood as referring to the software, i.e., the mathematical mapping of inputs to outputs. These two interpretations are by no means distinct: each logical component is implemented as the evolution of a physical component in some state. Accordingly, the logical requirements of a computation also specify the minimal physical requirements of the computational device. In quantum computational processes, the physical components are constructed from materials whose states and evolutions are described by quantum mechanics. At the logical level, this permits the use of quantum information theory: states are represented by vectors in a Hilbert space and evolutions are specified via unitary dynamics and measurements. In measurement-based quantum computational processes, the latter form of evolution, i.e. that driven by measurements, is most prominent. In this context, certain quantum states taken on the quality of a computational resource. That is to say, it is the combination of state and measurement together that produce the desired evolution for a given logical component. This thesis treats several topics related to the preparation and use of such resource states. In particular, much of the thesis will be concerned with states that support universal quantum computation; that is, for which any quantum computation is possible within the framework of MBQC. The first contribution in this regard consists in establishing a connection between a different framework of universal computation, namely that of parity quantum computing, and MBQC. This connection relates to both preparation and use since the former was developed in the context of quantum optimisation (a use) and utilises a specific type of encoding of quantum states (a preparation). The next sections consider the requirements under which specific sets of logical components suffice for universal quantum computation. These sets commonly arise in quantum information theory, and as state-measurement combinations in MBQC and parity quantum computing in particular. In addition to establishing results on the sizes of such sets, this thesis investigates the consequences for parity quantum computing and MBQC, including, e.g., considerations for the design of physical devices and the compilation of computations. Finally, several limits to the preparation and use of states for MBQC are investigated. In one case, an information-theoretic quantity is considered which can be used to quantify uncertainty regarding some piece of information. In the context of MBQC, the piece of information can pertain to, e.g., the choice of computation to perform on a given state, such as in the context of blind quantum computing. Thereafter, a method is developed capable of witnessing the inability to prepare various states under certain constraints that are relevant in, e.g., the context of quantum networks.