Graph states are computationally powerful quantum states with many applications, including use as resource states for measurement-based quantum computing (MBQC). We demonstrate construction of graph states on a Rydberg atom quantum analog simulator. We show how an always-on interaction can be used to simultaneously entangle all Rydberg atoms into a graph state. We construct and implement many-body computational order parameters for graph states using nonlocal measurement-based logic operations in the Clifford group. The order parameters measure the efficacy of entanglement to allow MBQC on graph states of any size. We parametrize finite-size scaling of these order parameters. Our results define a route to efficiently test computational power in quantum devices.
Graph states are computationally powerful quantum states with many applications, including use as resource states for measurement-based quantum computing (MBQC). We demonstrate construction of graph states on a Rydberg atom quantum analog simulator. We show how an always-on interaction can be used to simultaneously entangle all Rydberg atoms into a graph state. We construct and implement many-body computational order parameters for graph states using nonlocal measurement-based logic operations in the Clifford group. The order parameters measure the efficacy of entanglement to allow MBQC on graph states of any size. We parametrize finite-size scaling of these order parameters. Our results define a route to efficiently test computational power in quantum devices.
The framework of measurement-based quantum computation (MBQC) allows us to view the ground states of local Hamiltonians as potential resources for universal quantum computation. A central goal in this field is to find models with ground states that are universal for MBQC and that are also natural in the sense that they involve only two-body interactions and have a small local Hilbert space dimension. Graph states are the original resource states for MBQC, and while it is not possible to obtain graph states as exact ground states of two-body Hamiltonians here we construct two-body frustration-free Hamiltonians that have arbitrarily good approximations of graph states as unique ground states. The construction involves taking a two-body frustration-free model that has a ground state convertible to a graph state with stochastic local operations, then deforming the model such that its ground state is close to a graph state. Each graph state qubit resides in a subspace of a higher dimensional particle. This deformation can be applied to two-body frustration-free Affleck-Kennedy-Lieb-Tasaki (AKLT) models, yielding Hamiltonians that are exactly solvable with exact tensor network expressions for ground states. For the star-lattice AKLT model, the ground state of which is not expected to be a universal resource for MBQC, applying such a deformation appears to enhance the computational power of the ground state, promoting it to a universal resource for MBQC. Transitions in computational power, similar to percolation phase transitions, can be observed when Hamiltonians are deformed in this way. Improving the fidelity of the ground state comes at the cost of a shrinking gap. While analytically proving gap properties for these types of models is difficult in general, we provide a detailed analysis of the deformation of a spin-1 AKLT state to a linear graph state.
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.
The direct compilation of algorithm-specific graph states in measurement-based quantum computation (MBQC) can lead to resource reductions in terms of circuit depth, entangling gates, and even the number of physical qubits. In this work, we extend previous studies on algorithm-tailored graph states to periodic sequences of generalized Pauli rotations, which commonly appear in, e.g., Trotterized Hamiltonian simulation. We first implement an enhanced simulated-annealing-based algorithm to find optimal periodic graph states within local-Clifford equivalent MBQC resources. In addition, we derive a novel scheme for the preparation of resource states based on a graph state and a ladder of CNOT gates, which we term anticommutation-based MBQC, since it uncovers a direct relationship between the graph state and the anticommutation matrix for the set of Hamiltonians generating the computation. We also deploy our two approaches to derive universal resource states from minimal universal sets of generating Hamiltonians. Finally, we demonstrate and compare both of our methods based on various examples from condensed matter physics and universal quantum computation.
Measurement-based quantum computation (MBQC) performs quantum algorithms by local, adaptive measurements on an initially entangled many-body "resource" state. This thesis investigates MBQC through two tightly coupled lenses: (i) which physical states and phases of matter constitute universal resources, and (ii) how the temporal order induced by measurement adaptivity constrains and, in turn, is constrained by those resources. Resources from valence-bond constructions. We develop hybrid AKLT-type (valence-bond) resources on two-dimensional lattices and show how a generalized POVM reduces higher-spin degrees of freedom to effective qubits while preserving computational viability. We analyze worst-case and frustrated geometries (e.g., kagome and decorated lattices), identify planarity-restoring local operations, and use percolation-style diagnostics on the induced graph states to certify universality beyond idealized cluster-state settings. A two-parameter phase with noisy POVMs. Extending ground states across a phase connected to the AKLT point, we introduce a measurement-noise–aware framework with probabilistic restoration and closed-form weight formulae derived via a graphical (g-)calculus. Large-scale numerics that account for correlations map a two-parameter phase diagram and delineate regimes of universal vs. non-universal post-measurement graphs. These results exhibit a robust universal region that persists away from ideal measurements and clarify how noise and Hamiltonian deformation jointly control computational power. Temporal order and determinism. We develop a stabilizer-and-influence-matrix formalism that places temporal dependencies on the same footing as resource structure. Four theorems establish a two-way determination between (a) the classical processing relations (including the influence matrix that generates the partial order of measurements) and (b) the resource stabilizer in a normal form, up to local equivalence. This links gauge freedoms, byproduct handling, and flow/gflow–style constraints into a unified picture of when adaptive measurement schedules yield deterministic computation. Together, these contributions clarify when physically motivated ground states serve as universal MBQC resources under realistic measurement noise, and how temporal constraints fundamentally shape the space of admissible computations in MBQC.
Abstract The paradigm of measurement-based quantum computing (MBQC) starts from a highly entangled resource state on which unitary operations are executed through adaptive measurements and corrections ensuring determinism. This is set in contrast to the more common quantum circuit model, in which unitary operations are directly implemented through quantum gates prior to final measurements. In this work, we incorporate concepts from MBQC into the circuit model to create a hybrid simulation technique, permitting us to split any quantum circuit into a classically efficiently simulatable Clifford-part and a second part consisting of a stabilizer state and local (adaptive) measurement instructions—a so-called standard form—which is executed on a quantum computer. We further process the stabilizer state with the graph state formalism, thus, enabling a significant decrease in circuit depth for certain applications. We show that groups of mutually-commuting operators can be implemented using fully-parallel, i.e. non-adaptive, measurements within our protocol. In addition, we discuss how groups of mutually commuting observables can be simulatenously measured by adjusting the resource state, rather than performing a costly basis transformation prior to the measurement as it is done in the circuit model. Finally, we demonstrate the utility of our technique on two examples of high practical relevance—the Quantum Approximate Optimization Algorithm and the Variational Quantum Eigensolver (VQE) for the ground-state energy estimation of the water molecule. For the VQE, we find a reduction of the depth by a factor of 4 to 5 using measurement patterns vs. the standard circuit model. At the same time, since we incorporate the simultaneous measurements, our patterns allow us to save shots by a factor of at least 3.5 compared to measuring Pauli strings individually in the circuit model.
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.