Entanglement, Flow and Classical Simulatability in Measurement Based Quantum Computation

Damian Markham, Elham Kashefi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

The question of which and how a particular class of entangled resource states (known as graph states) can be used for measurement based quantum computation (MBQC) recently gave rise to the notion of Flow and its generalisation gFlow. That is a causal structure for measurements guaranteeing deterministic computation. Furthermore, gFlow has proven itself to be a powerful tool in studying the difference between the measurement-based and circuit models for quantum computing, as well as analysing cryptographic protocols. On the other hand, entanglement is known to play a crucial role in MBQC. In this paper we first show how gFlow can be used to directly give a bound on the classical simulation of an MBQC. Our method offers an interpretation of the gFlow as showing how information flows through a computation, giving rise to an information light cone.We then establish a link between entanglement and the existence of gFlow for a graph state. We show that the gFlow can be used to upper bound the entanglement width and what we call the structural entanglement of a graph state. In turn this gives another method relating the gFlow to upper bound on how efficiently a computation can be simulated classically. These two methods of getting bounds on the difficulty of classical simulation are different and complementary and several known results follow. In particular known relations between the MBQC and the circuit model allow these results to be translated across models.
Original languageEnglish
Title of host publicationHorizons of the Mind. A Tribute to Prakash Panangaden
Subtitle of host publicationEssays Dedicated to Prakash Panangaden on the Occasion of His 60th Birthday
PublisherSpringer International Publishing
Number of pages27
ISBN (Electronic)978-3-319-06880-0
ISBN (Print)978-3-319-06879-4
Publication statusPublished - 2014

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Dive into the research topics of 'Entanglement, Flow and Classical Simulatability in Measurement Based Quantum Computation'. Together they form a unique fingerprint.

Cite this