Abstract For certain restricted computational tasks, quantum mechanics provides a provable advantage over any possible classical implementation. Several of these results have been proven using the framework of measurement-based quantum computation (MBQC), where nonlocality and more generally contextuality have been identified as necessary resources for certain quantum computations. Here, we consider the computational power of MBQC in more detail by refining its resource requirements, both on the allowed operations and the number of accessible qubits. More precisely, we identify which Boolean functions can be computed in non-adaptive MBQC, with local operations contained within a finite level in the Clifford hierarchy. Moreover, for non-adaptive MBQC restricted to certain subtheories such as stabiliser MBQC, we compute the minimal number of qubits required to compute a given Boolean function. Our results point towards hierarchies of resources that more sharply characterise the power of MBQC beyond the binary of contextuality vs non-contextuality.
Abstract For certain restricted computational tasks, quantum mechanics provides a provable advantage over any possible classical implementation. Several of these results have been proven using the framework of measurement-based quantum computation (MBQC), where nonlocality and more generally contextuality have been identified as necessary resources for certain quantum computations. Here, we consider the computational power of MBQC in more detail by refining its resource requirements, both on the allowed operations and the number of accessible qubits. More precisely, we identify which Boolean functions can be computed in non-adaptive MBQC, with local operations contained within a finite level in the Clifford hierarchy. Moreover, for non-adaptive MBQC restricted to certain subtheories such as stabiliser MBQC, we compute the minimal number of qubits required to compute a given Boolean function. Our results point towards hierarchies of resources that more sharply characterise the power of MBQC beyond the binary of contextuality vs non-contextuality.
Contextuality—the obstruction to describing quantum mechanics in a classical statistical way—has been proposed as a resource that powers quantum computing. The measurement-based model provides a concrete manifestation of contextuality as a computational resource, as follows. If local measurements on a multi-qubit state can be used to evaluate nonlinear boolean functions with only linear control processing, then this computation constitutes a proof of strong contextuality—the possible local measurement outcomes cannot all be pre-assigned. However, this connection is restricted to the special case when the local measured systems are qubits , which have unusual properties from the perspective of contextuality. A single qubit cannot allow for a proof of contextuality, unlike higher-dimensional systems, and multiple qubits can allow for state-independent contextuality with only Pauli observables, again unlike higher-dimensional generalisations. Here we identify precisely that strong non-locality is necessary in a qudit measurement-based computation (MBC) that evaluates high-degree polynomial functions with only linear control. We introduce the concept of local universality , which places a bound on the space of output functions accessible under the constraint of single-qudit measurements. Thus, the partition of a physical system into subsystems plays a crucial role for the increase in computational power. A prominent feature of our setting is that the enabling resources for qubit and qudit MBC are of the same underlying nature, avoiding the pathologies associated with qubit contextuality.
Several classes of quantum circuits have been shown to provide a quantum computational advantage under certain assumptions. The study of ever more restricted classes of quantum circuits capable of quantum advantage is motivated by possible simplifications in experimental demonstrations. In this paper we study the efficiency of measurement-based quantum computation with a completely flat temporal ordering of measurements. We propose new constructions for the deterministic computation of arbitrary Boolean functions, drawing on correlations present in multi-qubit Greenberger, Horne, and Zeilinger (GHZ) states. We characterize the necessary measurement complexity using the Clifford hierarchy, and also generally decrease the number of qubits needed with respect to previous constructions. In particular, we identify a family of Boolean functions for which deterministic evaluation using non-adaptive MBQC is possible, featuring quantum advantage in width and number of gates with respect to classical circuits.
In measurement-based quantum computation (MBQC), a special highly entangled state (called a resource state) allows for universal quantum computation driven by single-qubit measurements and postmeasurement corrections. The large number of qubits necessary to construct the resource state constitutes one of the main down sides to MBQC. However, in some instances it is possible to extend the resource state on the fly, meaning that not every qubit must be realized in the devices simultaneously. We consider the question of the minimal number of physical qubits that must be present in a system to directly implement a given measurement pattern. For measurement patterns which have quantum circuit representation as formalized by the notion of flow, with n inputs, n outputs, and m total qubits, we show that only a minimum of n+1 and m qubits are required, while the number of required qubits can be as high as $m\ensuremath{-}2$ for measurement patterns which implement a unitary but do not have a quantum circuit representation, as formalized by the notion of generalized flow (gflow). We discuss the implications of removing the Clifford part of a measurement pattern, using well-established transformation rules for Pauli measurements, for the presence of flow versus gflow, and hence the effect on the minimum number of physical qubits required to directly realize the measurement pattern.
We combine the study of resources in measurement-based quantum computation (MBQC) with that of quantum solutions to linear constraint systems (LCS). Contextuality of the input state in MBQC has been identified as a key resource for quantum advantage, and in a stronger form, underlies algebraic relations between (measurement) operators which obey classically unsatisfiable (linear) constraints. Here, we compare these two perspectives on contextuality, and study to what extent they are related. More precisely, we associate a LCS to certain MBQC which exhibit strong forms of state-dependent contextuality, and ask if the measurement operators in such MBQC give rise to state-independent contextuality in the form of quantum solutions of its associated LCS. Our main result rules out such quantum solutions for a large class of MBQC. This both sharpens the distinction between state-dependent and state-independent forms of contextuality, and further generalises results on the non-existence of quantum solutions to LCS in finite odd (prime) dimension.
Measurement-based quantum computation (MBQC) is a universal model of quantum computation whose full power requires adaptivity. Contextuality is known to power quantum advantage in MBQC, yet it has resisted algebraic analysis in the adaptive setting.
We show that if an adaptive Z2-linear measurement-based quantum computing protocol deterministically computes a non-affine Boolean function, then the underlying quantum resource satisfies an inconsistent set of linear equations. This witnesses an algebraic form of strong contextuality generalising Mermin's All-versus-Nothing arguments. Such algebraic contextuality can be detected cohomologically, resolving an open question posed by Raussendorf, who had established cohomological witnesses of contextuality for non-adaptive protocols, but left the adaptive case open. We prove this result constructively: we model adaptive measurement protocols as ordinary measurements on a larger scenario of tree-like measurements, and explicitly build the inconsistent equations inductively.
Measurement-based quantum computation (or the one-way quantum computation) is a model in which a series of adaptive single qubit measurements upon an entangled resource state can produce classical output data equivalent to an arbitrary quantum logic circuit. Loosely speaking, the correlations in these measurements can be considered the resource which allows the computation to be performed. Bell inequalities demonstrate that quantum mechanics permits the outcomes of sets of measurements to be correlated in ways incompatible with the predictions of any local hidden variable theory, including classical physics. In the Bell inequality, and multi-party generalisations, a set of single-qubit measurements are performed, on spatially separated systems. Correlations in these measurements can act as a signature that no local hidden variable description of the experiment is possible. At first sight, we see superficial similarities between these settings. In both cases, non-classical correlations play a central role. However, there are also some key differences. Most importantly, measurement-based quantum computing requires adaptive measurements, at odds with the spatial-separated nature of Bell inequality experiments. Nevertheless some striking connections have been reported [1], [2] particularly between GHZ-type paradoxes and deterministic MBQC computations, and between CHSH-type Bell inequalities and non-deterministic MBQC correlations [1], [3]. In my talk I will survey these works and some recent results [3], [4] from my group at UCL, in which a number of connections between multi-party Bell inequalities and MBQC are explored. [1] J. Anders and D.E. Browne, "The Computational Power of Correlations", Physical Review Letters 102, 050502 (2009) [2] R. Raussendorf, "Quantum computation, discreteness, and contextuality", arxiv:0907.5449 [3] M. J. Hoban, E.T. Campbell, K. Loukopolous, D.E. Browne, "Non-adaptive measurement-based quantum computation and multi-party Bell inequalties", in preparation. [4] M. J. Hoban and D.E. Browne, in preparation.