### 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.

Original language | English |
---|---|

Pages (from-to) | 307-331 |

Number of pages | 25 |

Journal | Electronic Notes in Theoretical Computer Science |

Volume | 249 |

DOIs | |

Publication status | Published - 8 Aug 2009 |

Event | 25th Conference on Mathematical Foundations of Programming Semantics (MFPS 2009) - Oxford, United Kingdom Duration: 3 Apr 2009 → 7 Apr 2009 |

### Fingerprint

### Keywords

- ancilla-driven
- graph states
- quantum computation
- universal quantum computation

### Cite this

*Electronic Notes in Theoretical Computer Science*,

*249*, 307-331. https://doi.org/10.1016/j.entcs.2009.07.096

}

*Electronic Notes in Theoretical Computer Science*, vol. 249, pp. 307-331. https://doi.org/10.1016/j.entcs.2009.07.096

**Twisted graph states for ancilla-driven universal quantum computation.** / Kashefi, E.; Oi, D. K L; Browne, D.; Anders, J.; Andersson, E.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Twisted graph states for ancilla-driven universal quantum computation

AU - Kashefi, E.

AU - Oi, D. K L

AU - Browne, D.

AU - Anders, J.

AU - Andersson, E.

PY - 2009/8/8

Y1 - 2009/8/8

N2 - 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.

AB - 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.

KW - ancilla-driven

KW - graph states

KW - quantum computation

KW - universal quantum computation

UR - http://www.scopus.com/inward/record.url?scp=68549130596&partnerID=8YFLogxK

U2 - 10.1016/j.entcs.2009.07.096

DO - 10.1016/j.entcs.2009.07.096

M3 - Article

AN - SCOPUS:68549130596

VL - 249

SP - 307

EP - 331

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

SN - 1571-0661

ER -