In measurement-based quantum computing, there is a natural ``causal cone'' among qubits of the resource state, since the measurement angle on a qubit has to depend on previous measurement results in order to correct the effect of by-product operators. If we respect the no-signaling principle, by-product operators cannot be avoided. Here we study the possibility of acausal measurement-based quantum computing by using the process matrix framework [Oreshkov, Costa, and Brukner, Nat. Commun. 3, 1092 (2012)]. We construct a resource process matrix for acausal measurement-based quantum computing restricting local operations to projective measurements. The resource process matrix is an analog of the resource state of the standard causal measurement-based quantum computing. We find that if we restrict local operations to projective measurements the resource process matrix is (up to a normalization factor and trivial ancilla qubits) equivalent to the decorated graph state created from the graph state of the corresponding causal measurement-based quantum computing. We also show that it is possible to consider a causal game whose causal inequality is violated by acausal measurement-based quantum computing.
In measurement-based quantum computing, there is a natural ``causal cone'' among qubits of the resource state, since the measurement angle on a qubit has to depend on previous measurement results in order to correct the effect of by-product operators. If we respect the no-signaling principle, by-product operators cannot be avoided. Here we study the possibility of acausal measurement-based quantum computing by using the process matrix framework [Oreshkov, Costa, and Brukner, Nat. Commun. 3, 1092 (2012)]. We construct a resource process matrix for acausal measurement-based quantum computing restricting local operations to projective measurements. The resource process matrix is an analog of the resource state of the standard causal measurement-based quantum computing. We find that if we restrict local operations to projective measurements the resource process matrix is (up to a normalization factor and trivial ancilla qubits) equivalent to the decorated graph state created from the graph state of the corresponding causal measurement-based quantum computing. We also show that it is possible to consider a causal game whose causal inequality is violated by acausal measurement-based quantum computing.
Measurement-based quantum computation is a novel model of quantum computing where universal quantum computation can be done with only local measurements on each particle of a quantum many-body state, which is called a resource state. One large difference of the measurement-based model from the circuit model is the existence of byproducts. In the circuit model, a desired unitary U can be implemented deterministically, whereas the measurement-based model implements BU, where B is an additional operator, which is called a byproduct. In order to compensate byproducts, following measurement angles must be adjusted. Such a feed-forwarding requires some classical processing and tuning of the measurement device, which cause the delay of computation and the additional decoherence. Is there any byproduct-free resource state? Here we show that if we respect the no-signaling principle, which is one of the most fundamental principles of physics, no universal resource state can avoid byproducts.
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.
In measurement-based quantum computation (MBQC), elementary quantum operations can be more parallelized than the quantum circuit model by employing a larger Hilbert space of graph states used as the resource. Thus MBQC can be regarded as a method of quantum computation where the temporal resource described by the depth of quantum operations can be reduced compared to the quantum circuit model by using the extra spatial resource described by graph states. To analyze the trade-off relationship of the spatial and temporal resources, we consider a method to obtain quantum circuit decompositions of general unitary transformations represented by MBQC on graph states with a certain underlying geometry called generalized flow. We present a method to translate any MBQC with generalized flow into quantum circuits without extra spatial resource. We also show an explicit way to unravel acausal gates without postselection that appear in the quantum circuit decomposition derived by a translation method [V. Danos and E. Kashefi, Phys. Rev. A 74, 052310 (2006)] and that represents an effect of the reduction of the temporal resource in MBQC. Finally, by considering a way to deterministically simulate these acausal gates, we investigate a general framework to analyze the trade-off between the spatial and temporal resources for quantum computation.
Measurement-Based Quantum Computing (MBQC) is an alternative to the quantum circuit model, whereby the computation proceeds via measurements on an entangled resource state. Noise processes are a major experimental challenge to the construction of a quantum computer. Here, we investigate how noise processes affecting physical states affect the performed computation by considering MBQC on a one-dimensional cluster state. This allows us to break down the computation in a sequence of building blocks and map physical errors to logical errors. Next, we extend the Matrix Product State construction to mixed states (which is known as Matrix Product Operators) and once again map the effect of physical noise to logical noise acting within the correlation space. This approach allows us to consider more general errors than the conventional Pauli errors, and could be used in order to simulate noisy quantum computation.
Measurement-based quantum computation (MBQC) is a model of quantum computation, in which computation proceeds via adaptive single qubit measurements on a multiqubit quantum state. It is computationally equivalent to the circuit model. Unlike the circuit model, however, its classical analog is little studied. Here we present a classical analog of MBQC whose computational complexity presents a rich structure. To do so, we identify uniform families of quantum computations [refining the circuits introduced by Bremner Proc. R. Soc. A 467, 459 (2010)] whose output is likely hard to exactly simulate (sample) classically. We demonstrate that these circuit families can be efficiently implemented in the MBQC model without adaptive measurement and, thus, can be achieved in a classical analog of MBQC whose resource state is a probability distribution which has been created quantum mechanically. Such states (by definition) violate no Bell inequality, but, if widely held beliefs about computational complexity are true, they, nevertheless, exhibit nonclassicality when used as a computational resource—an imprint of their quantum origin.
This thesis considers various paradigms of quantum computation in an attempt to understand the nature of the underlying physics. A standard approach is to consider unitary computation on pure input states, such that the outcome of the computation is determined by single computational basis measurement on the output state. It has been shown that there exists equivalent models of computation, such as measurement based quantum computing (MBQC), which provide insight into the role of entanglement and measurement. Furthermore, constraining or relaxing available resources can directly impacts the power of the computation, allowing one to gauge their role in the process. Here, we first extend known constructions such as Matrix Product States, MBQC and the oneclean qubit model to a mixed state formalism, in an attempt to develop computational models where noise acting on the physical resources, as might be experienced in laboratory settings, may be mapped to logical noise on the computation. Next, we introduce Measurement-Based Classical Computing, an essentially classical model of computation, wherein the complexity hard wired into probability distributions generated via quantum means yields surprising non classical results. Finally, we consider postselection the ability to discard displeasing measurement outcomes and argue that it may be used in a tame way, which does not provide a dramatic increase in computational power. From here, we develop a new Hamiltonian, based on a circuit to Hamiltonian construction, presenting evidence of QMA-hardness.