© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Electronic Notes in Theoretical Computer Science

Twisted Graph States for Ancilla-driven Universal Quantum Computation

Elham Kashefi, Daniel K. L. Oi, Dan E. Browne, Janet Anders, Erika Andersson

Published Aug 1, 2009• 23 citations

Abstract

We introduce a new paradigm for quantum computing called Ancilla-Driven Quantum Computation (ADQC) which combines aspects both of the quantum circuit [D. Deutsch. Quantum computational networks. Proc. Roy. Soc. Lond A, 425, 1989] and the one-way model [R. Raussendorf and H. J. Briegel. A one-way quantum computer. Physical Review Letters, 86, 2001] to overcome challenging issues in building large-scale quantum computers. Instead of directly manipulating each qubit to perform universal quantum logic gates or measurements, ADQC uses a fixed two-qubit interaction to couple the memory register of a quantum computer to an ancilla qubit. By measuring the ancilla, the measurement-induced back-action on the system performs the desired logical operations. The underlying mathematical model is based on a new entanglement resource called twisted graph states generated from non-commuting operators, leading to a surprisingly powerful structure for parallel computation compared to graph states obtained from commuting generators. [M. Hein, J. Eisert, and H.J. Briegel. Multi-party entanglement in graph states. Physical Review A, 69, 2004. quant-ph/0307130]. The ADQC model is formalised in an algebraic framework similar to the Measurement Calculus [V. Danos, E. Kashefi, and P. Panangaden. The measurement calculus. Journal of ACM, 2007]. Furthermore, we present the notion of causal flow for twisted graph states, based on the stabiliser formalism, to characterise the determinism. Finally we demonstrate compositional embedding between ADQC and both the one-way and circuit models which will allow us to transfer recently developed theory and toolkits of measurement-based quantum computing and quantum circuit models directly into ADQC.

DOI: 10.1016/j.entcs.2009.07.096

Related papers

Ancilla Driven Quantum Computation with Arbitrary Entangling Strength

Kerem Halil Shah, Daniel K. L. Oi

We extend the model of Ancilla Driven Quantum Computation (ADQC) by considering gates with arbitrary entangling power. By giving up stepwise determinism, universal QC can still be achieved through a variable length sequence of single qubit gates and probabilistic "repeat-until-succes" entangling operations. This opens up a new range of possible physical implementations as well as shedding light on the sets of resources sufficient for universal QC.

Leibniz international proceedings in informatics•Jan 1, 2013•4 citations

The measurement calculus

Vincent Danos A, Elham Kashefi, Prakash Panangaden

Measurement-based quantum computation has emerged from the physics community as a new approach to quantum computation where the notion of measurement is the main driving force of computation. This is in contrast with the more traditional circuit model that is based on unitary operations. Among measurement-based quantum computation methods, the recently introduced one-way quantum computer [Raussendorf and Briegel 2001] stands out as fundamental. We develop a rigorous mathematical model underlying the one-way quantum computer and present a concrete syntax and operational semantics for programs, which we call patterns , and an algebra of these patterns derived from a denotational semantics. More importantly, we present a calculus for reasoning locally and compositionally about these patterns. We present a rewrite theory and prove a general standardization theorem which allows all patterns to be put in a semantically equivalent standard form. Standardization has far-reaching consequences: a new physical architecture based on performing all the entanglement in the beginning, parallelization by exposing the dependency structure of measurements and expressiveness theorems. Furthermore we formalize several other measurement-based models, for example, Teleportation, Phase and Pauli models and present compositional embeddings of them into and from the one-way model. This allows us to transfer all the theory we develop for the one-way model to these models. This shows that the framework we have developed has a general impact on measurement-based computation and is not just particular to the one-way quantum computer.

Journal of the ACM•Apr 1, 2007•193 citations

Higher-dimensional ancilla-driven quantum computation

Timothy J Proctor, Viv M. Kendon

A model of universal quantum computation with qudits ($d$-level systems) is presented in which the gates are implemented on a register entirely via fixed-form sequential interactions with ancillary qudits followed by adaptive, variable basis measurements of these ancillas. The model maintains determinism via classical feed-forward of measurement outcomes in a similar fashion to the qudit one-way model. An embedding of the qudit one-way model is given which demonstrates that the hybrid quantum-classical advantages of one-way quantum computation are also inherent in the model presented here, including the ability to implement any Clifford gate in constant depth using multiple ancillas in parallel. A model which requires only fixed basis measurements is then presented, but due to the lack of adaptive controls it can only implement universal quantum computation in a stochastic sense. Interestingly, this scheme may then be altered to recover determinism by replacing ancilla measurements with ancilla preparation. These models provide an intuitive setting for understanding the interplay between the benefits gained from classical controls, measurements and state preparation in the context of multi-valued logic ancilla-based quantum computation.

•Oct 22, 2015•1 citation

Ancilla Driven Quantum Computation with arbitrary entangling strength

Kerem Halil Shah, Daniel K. L. Oi

We extend the model of Ancilla Driven Quantum Computation (ADQC) by considering gates with arbitrary entangling power. By giving up stepwise determinism, universal QC can still be achieved through a variable length sequence of single qubit gates and probabilistic "repeat-until-success" entangling operations. This opens up a new range of possible physical implementations as well as shedding light on the sets of resources sufficient for universal QC.

arXiv:1303.2066•Mar 8, 2013•9 citations

Ancilla-driven universal quantum computation

Janet Anders, Daniel K. L. Oi, Elham Kashefi +2 more

We introduce a model of quantum computation intermediate between the gate-based and measurement-based models. A quantum register is manipulated remotely with the help of a single ancilla that ``drives'' the evolution of the register. The fully controlled ancilla qubit is coupled to the computational register only via a fixed unitary two-qubit interaction and then measured in suitable bases, driving both single- and two-qubit operations on the register. Arbitrary single-qubit operations directly on register qubits are not needed. We characterize all interactions $E$ that induce a unitary, stepwise deterministic measurement back-action on the register sufficient to implement any quantum channel. Our scheme offers experimental advantages for computation, state preparation, and generalized measurements, since no tunable control of the register is required.

arXiv:0911.3783•Physical Review A•Aug 10, 2010•77 citations

Minimal ancilla-controlled quantum computation

Timothy J Proctor, Erika Andersson, Viv M. Kendon

We characterise a model of universal quantum computation where the register (computational) qubits are controlled by ancillary qubits, using only a single fixed interaction between register and ancillary qubits. No additional access is required to the computational register and the dynamics of both the register and ancilla are unitary. This scheme is inspired by the measurement-based ancilla-driven quantum computation of Anders et al. [PRA 82, 020301(R), 2010], but does not require measurements of the ancillas, and in this respect is similar to the original gate based model of quantum computation. We consider what possible forms this ancilla-register interaction can take, with a proof that the interaction is necessarily locally equivalent to SWAP combined with an entangling controlled gate. We further show which Hamiltonians can create such interactions and discuss two examples; the two-qubit XY Hamiltonian and a particular case of the XXZ Hamiltonian. We then give an example of a simple, finite and fault tolerant gate set for universal quantum computation in this model.

•Jul 23, 2013•0 citations

We introduce a new paradigm for quantum computing called Ancilla-Driven Quantum Computation (ADQC) which combines aspects both of the quantum circuit [D. Deutsch. Quantum computational networks. Proc. Roy. Soc. Lond A, 425, 1989] and the one-way model [R. Raussendorf and H. J. Briegel. A one-way quantum computer. Physical Review Letters, 86, 2001] to overcome challenging issues in building large-scale quantum computers. Instead of directly manipulating each qubit to perform universal quantum logic gates or measurements, ADQC uses a fixed two-qubit interaction to couple the memory register of a quantum computer to an ancilla qubit. By measuring the ancilla, the measurement-induced back-action on the system performs the desired logical operations. The underlying mathematical model is based on a new entanglement resource called twisted graph states generated from non-commuting operators, leading to a surprisingly powerful structure for parallel computation compared to graph states obtained from commuting generators. [M. Hein, J. Eisert, and H.J. Briegel. Multi-party entanglement in graph states. Physical Review A, 69, 2004. quant-ph/0307130]. The ADQC model is formalised in an algebraic framework similar to the Measurement Calculus [V. Danos, E. Kashefi, and P. Panangaden. The measurement calculus. Journal of ACM, 2007]. Furthermore, we present the notion of causal flow for twisted graph states, based on the stabiliser formalism, to characterise the determinism. Finally we demonstrate compositional embedding between ADQC and both the one-way and circuit models which will allow us to transfer recently developed theory and toolkits of measurement-based quantum computing and quantum circuit models directly into ADQC.

Measurement-based quantum computation has emerged from the physics community as a new approach to quantum computation where the notion of measurement is the main driving force of computation. This is in contrast with the more traditional circuit model that is based on unitary operations. Among measurement-based quantum computation methods, the recently introduced one-way quantum computer [Raussendorf and Briegel 2001] stands out as fundamental. We develop a rigorous mathematical model underlying the one-way quantum computer and present a concrete syntax and operational semantics for programs, which we call patterns , and an algebra of these patterns derived from a denotational semantics. More importantly, we present a calculus for reasoning locally and compositionally about these patterns. We present a rewrite theory and prove a general standardization theorem which allows all patterns to be put in a semantically equivalent standard form. Standardization has far-reaching consequences: a new physical architecture based on performing all the entanglement in the beginning, parallelization by exposing the dependency structure of measurements and expressiveness theorems. Furthermore we formalize several other measurement-based models, for example, Teleportation, Phase and Pauli models and present compositional embeddings of them into and from the one-way model. This allows us to transfer all the theory we develop for the one-way model to these models. This shows that the framework we have developed has a general impact on measurement-based computation and is not just particular to the one-way quantum computer.

A model of universal quantum computation with qudits (

d

-level systems) is presented in which the gates are implemented on a register entirely via fixed-form sequential interactions with ancillary qudits followed by adaptive, variable basis measurements of these ancillas. The model maintains determinism via classical feed-forward of measurement outcomes in a similar fashion to the qudit one-way model. An embedding of the qudit one-way model is given which demonstrates that the hybrid quantum-classical advantages of one-way quantum computation are also inherent in the model presented here, including the ability to implement any Clifford gate in constant depth using multiple ancillas in parallel. A model which requires only fixed basis measurements is then presented, but due to the lack of adaptive controls it can only implement universal quantum computation in a stochastic sense. Interestingly, this scheme may then be altered to recover determinism by replacing ancilla measurements with ancilla preparation. These models provide an intuitive setting for understanding the interplay between the benefits gained from classical controls, measurements and state preparation in the context of multi-valued logic ancilla-based quantum computation.

We introduce a model of quantum computation intermediate between the gate-based and measurement-based models. A quantum register is manipulated remotely with the help of a single ancilla that ``drives'' the evolution of the register. The fully controlled ancilla qubit is coupled to the computational register only via a fixed unitary two-qubit interaction and then measured in suitable bases, driving both single- and two-qubit operations on the register. Arbitrary single-qubit operations directly on register qubits are not needed. We characterize all interactions

E

that induce a unitary, stepwise deterministic measurement back-action on the register sufficient to implement any quantum channel. Our scheme offers experimental advantages for computation, state preparation, and generalized measurements, since no tunable control of the register is required.

We characterise a model of universal quantum computation where the register (computational) qubits are controlled by ancillary qubits, using only a single fixed interaction between register and ancillary qubits. No additional access is required to the computational register and the dynamics of both the register and ancilla are unitary. This scheme is inspired by the measurement-based ancilla-driven quantum computation of Anders et al. [PRA 82, 020301(R), 2010], but does not require measurements of the ancillas, and in this respect is similar to the original gate based model of quantum computation. We consider what possible forms this ancilla-register interaction can take, with a proof that the interaction is necessarily locally equivalent to SWAP combined with an entangling controlled gate. We further show which Hamiltonians can create such interactions and discuss two examples; the two-qubit XY Hamiltonian and a particular case of the XXZ Hamiltonian. We then give an example of a simple, finite and fault tolerant gate set for universal quantum computation in this model.