arXiv:1408.0745 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences

Topos logic in measurement-based quantum computation

Leon Loveridge, Raouf Dridi, Robert Raussendorf

Published Mar 11, 2015• 3 citations

Abstract

We report first steps towards elucidating the relationship between contextuality, measurement-based quantum computation (MBQC) and the non-classical logic of a topos associated with the computation. We show that, in a class of MBQC, classical universality requires non-classical logic, which is ‘consumed’ during the course of the computation, thereby pinpointing another potential quantum computational resource.

DOI: 10.1098/rspa.2014.0716

Related papers

Hierarchies of resources for measurement-based quantum computation

Markus Frembs, Sam Roberts, Earl T. Campbell +1 more

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.

arXiv:2203.09965New Journal of PhysicsDec 28, 202211 citations

Contextuality in measurement-based quantum computation

Robert Raussendorf

We show, under natural assumptions for qubit systems, that measurement-based quantum computations (MBQCs) which compute a nonlinear Boolean function with a high probability are contextual. The class of contextual MBQCs includes an example which is of practical interest and has a superpolynomial speedup over the best-known classical algorithm, namely, the quantum algorithm that solves the ``discrete log'' problem.

arXiv:0907.5449Physical Review AAug 19, 2013251 citations

Contextuality as a resource for measurement-based quantum computation beyond qubits

Markus Frembs, Sam Roberts, Stephen D. Bartlett

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.

arXiv:1804.07364New Journal of PhysicsSep 24, 201844 citations

No quantum solutions to linear constraint systems from monomial measurement-based quantum computation in odd prime dimension

Markus Frembs, Cihan Okay, Ho Yiu Chung

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.

quant-pharXiv:2601.11367Jan 19, 20260 citations

On resource states for measurement-based quantum computation

Eleanor Gilbert Rieffel, Howard M. Wiseman

We consider the issue of what should count as a resource for measurement-based quantum computation (MBQC). While a state that supports universal quantum computation clearly should be considered a resource, universality should not be necessary given the existence of interesting, but less computationally-powerful, classes of MBQCs. Here, we propose minimal criteria for a state to be considered a resource state for MBQC. Using these criteria, we explain why discord-free states cannot be resources for MBQC, contrary to recent claims [Hoban et al., arXiv:1304.2667v1]. Independently of our criteria, we also show that the arguments of Hoban et al., if correct, would imply that Shor's algorithm (for example) can be implemented by measuring discord-free states.

Jul 3, 20130 citations

Quantum Computation Beyond the Unitary Circuit Model

Naïri Usher

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.

Jun 28, 20170 citations