Abstract
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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Raussendorf, R., Briegel, H.J.: A one-way quantum computer. Physical Review Letters 86, 5188 (2001)
Anders, J., Browne, D.E.: Computational power of correlations. Physical Review Letters 102, 050502 (2009)
Hobanand, M.J., Wallman, J.J, Browne, D.E.: Generalized bell-inequality experiments and computation. Physical Review A 84(6), 062107 (2011)
Broadbent, A., Fitzsimons, J., Kashefi, E.: Universal blind quantum computing. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), p. 517 (2009)
Markham, D., Sanders, B.C.: Graph states for quantum secret sharing. Physical Review A 78, 042309 (2008)
Danos, V., Kashefi, E., Panangaden, P.: The measurement calculus. Journal of ACM 54, 8 (2007)
Vidal, G.: Efficient classical simulation of slightly entangled quantum computations. Physical Review Letters 91(14), 147902 (2003)
Yoran, N., Short, A.J.: Efficient classical simulation of the approximate quantum fourier transform. Physical Review A 76(4), 042321 (2007)
Van den Nest, M., Miyake, A., Dür, W., Briegel, H.J.: Universal resources for measurement-based quantum computation. Physical Review Letters 97(15), 150504 (2006)
Van den Nest, M., Dür, W., Vidal, G., Briegel, H.J.: Classical simulation versus universality in measurement-based quantum computation. Physical Review A 75(1), 012337 (2007)
Van den Nest, M., Dür, W., Miyake, A., Briegel, H.J.: Fundamentals of universality in one-way quantum computation. New Journal of Physics 9(6), 204 (2007)
Danos, V., Kashefi, E.: Determinism in the one-way model. Physical Review A 74, 052310 (2006)
Browne, D., Kashefi, E., Mhalla, M., Perdrix, S.: Generalized flow and determinism in measurement-based quantum computation. New Journal of Physics 9, 250 (2007)
Hein, M., Eisert, J., Briegel, H.J.: Multi-party entanglement in graph states. Physical Review A 69(6), 062311 (2004)
de Beaudrap, N.: Finding flows in the one-way measurement model. Phys. Rev. A 77, 022328, 8 (2006, 2008)
Mhalla, M., Perdrix, S.: Finding optimal flows efficiently. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 857–868. Springer, Heidelberg (2008)
de Beaudrap, N.: Unitary-circuit semantics for measurement-based computations. International Journal of Quantum Information (IJQI) 8, 1 (2009)
Kashefi, E., Markham, D., Mhalla, M., Perdrix, S.: Information flow in secret sharing protocols. Electron. Notes Theor. Comput. Sci. 9 (2009)
de Beaudrap, N., Danos, V., Kashefi, E., Roetteler, M.: Quadratic form expansions for unitaries. In: Kawano, Y., Mosca, M. (eds.) TQC 2008. LNCS, vol. 5106, pp. 29–46. Springer, Heidelberg (2008)
Broadbent, A., Kashefi, E.: Parallelizing quantum circuits. Theoretical Computer Science 410(26), 2489 (2009)
Kashefi., E., da Silva, R.D., Galvao, E.F.: Closed timelike curves in measurement-based quantum computation. Phys. Rev. A 83, 012316 (2011)
Raussendorf, R., Sarvepalli, P., Wei, T.-C., Haghnegahdar, P.: Measurement-based quantum computation–a quantum-meachanical toy model for spacetime? arXiv:1108.5774 (2011)
Raussendorf, R., Sarvepalli, P., Wei, T.-C., Haghnegahdar, P.: Symmetry constraints on temporal order in measurement-based quantum computation. Electronic Proceedings in Theoretical Computer Science (EPTCS) 95, 219 (2012)
Jozsa, R.: On the simulation of quantum circuits. quant-ph/0603163 (2006)
Perdrix, S., Marin, A., Markham, D.: Access structure in graphs in high dimension and application to secret sharing. In: Proceedings of the Eighth Conference on the Theory of Quantum Computation, Communication and Cryptography (2013)
Mhalla, M., Murao, M., Perdrix, S., Someya, M., Turner, P.S.: Which graph states are useful for quantum information processing? In: Proceedings of the Sixth Conference on the Theory of Quantum Computation, Communication and Cryptography (2011)
Browne, D., Briegel, H.J.: One-way quantum computation. In: Lectures on Quantum Information, p. 359. Wiley Online Library (2006)
Antonio, B., Markham, D., Anders, J.: Trade-off between computation time and hamiltonian degree in adiabatic graph-state quantum computation. arXiv:1309.1443 (2013)
Browne, D.E., Kashefi, E., Perdrix, S.: Computational depth complexity of measurement-based quantum computation. In: Proceedings of the Fifth Conference on the Theory of Quantum Computation, Communication and Cryptography, p. 35 (2010)
Gottesman, D.: Stabilizer Codes and Quantum Error Correction. PhD thesis, California Institute of Technology (1997)
Gottesman, D.: The heisenberg representation of quantum computers, talk at. In: International Conference on Group Theoretic Methods in Physics (1998)
Raussendorf, R., Browne, D.E., Briegel, H.J.: Measurement-based quantum computation with cluster states. Physical Review A 68, 022312 (2003)
Nielsen, M.A.: Cluster-state quantum computation. Reports on Mathematical Physics 57, 147 (2005)
Deutsch, D., Hayden, P.: Information flow in entangled quantum systems. In: Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, vol. 456, p. 1759 (2000)
Diestel, R.: Graph Theory, 4th edn. Springer (2010)
Murao, M., Miyazaki, J., Hajdušek, M.: Translating measurement-based quantum computation with gflow into quantum circuit. arXiv:1306.2724 (2013)
Linden, N., Clark, S., Jozsa, R.: Generalised clifford groups and simulation of associated quantum circuits. arXiv:0701103 (2007)
Vidal, G.: A class of quantum many-body states that can be efficiently simulated. Phys. Rev. Lett. 101(110501) (2008)
Anders, J., Hajdušek, M., Markham, D., Vedral, V.: How much of one-way computation is just thermodynamics? Found. Phys. 38 (2008)
Markham, D., Anders, J., Hajdušek, M., Vedral, V.: Measurement based quantum computation on fractal lattices. In: EPTCS 26 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Markham, D., Kashefi, E. (2014). Entanglement, Flow and Classical Simulatability in Measurement Based Quantum Computation. In: van Breugel, F., Kashefi, E., Palamidessi, C., Rutten, J. (eds) Horizons of the Mind. A Tribute to Prakash Panangaden. Lecture Notes in Computer Science, vol 8464. Springer, Cham. https://doi.org/10.1007/978-3-319-06880-0_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-06880-0_22
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06879-4
Online ISBN: 978-3-319-06880-0
eBook Packages: Computer ScienceComputer Science (R0)