Twisted graph states for ancilla-driven universal quantum computation

E. Kashefi, D. K L Oi, D. Browne, J. Anders, E. Andersson

Research output: Contribution to journalArticle

16 Citations (Scopus)

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.

Fingerprint

Quantum computers
Quantum Computation
Quantum Computer
Qubit
Graph in graph theory
Quantum Circuits
Quantum Computing
Entanglement
Calculus
Quantum Logic
Determinism
Networks (circuits)
Parallel Computation
Model
Paradigm
Logic gates
Generator
Mathematical Model
Resources
Operator

Keywords

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

Cite this

Kashefi, E. ; Oi, D. K L ; Browne, D. ; Anders, J. ; Andersson, E. / Twisted graph states for ancilla-driven universal quantum computation. In: Electronic Notes in Theoretical Computer Science. 2009 ; Vol. 249. pp. 307-331.
@article{c2816b88b004499da357406079f1ccee,
title = "Twisted graph states for ancilla-driven universal quantum computation",
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.",
keywords = "ancilla-driven, graph states, quantum computation, universal quantum computation",
author = "E. Kashefi and Oi, {D. K L} and D. Browne and J. Anders and E. Andersson",
year = "2009",
month = "8",
day = "8",
doi = "10.1016/j.entcs.2009.07.096",
language = "English",
volume = "249",
pages = "307--331",
journal = "Electronic Notes in Theoretical Computer Science",
issn = "1571-0661",

}

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

In: Electronic Notes in Theoretical Computer Science, Vol. 249, 08.08.2009, p. 307-331.

Research output: Contribution to journalArticle

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

VL - 249

SP - 307

EP - 331

JO - Electronic Notes in Theoretical Computer Science

T2 - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

SN - 1571-0661

ER -