Colorado School of Mines, Department of Physics
"Quantum Complexity and Entangled Quantum Cellular Automata: A New Direction for Quantum Simulators"
Abstract: Ultracold quantum simulators have proven a tremendous success. These analog quantum computers have allowed us to explore diverse quantum many-body phenomena from quantum phase transitions to the Kibble-Zurek mechanism to many-body localization. We propose a new direction for analog quantum computations, quantum complexity. Despite hundreds of thousands of empirical examples of complexity ranging from complex networks like the internet to diverse mixed geometry microbial communities like the microbiome found in the human gut, we have no first principles theory of complexity – we don’t know why nature seems to prefer complexity. Moreover, unlike the other senses of the word “macroscopicity” we don’t have a good sense of how classical complexity, associated with macroscopic classical systems, results from the underlying quantum dynamics – so we don’t know where this preference first appears at the quantum level. In this talk, we focus on entangled dynamics of quantum cellular automata. Cellular automata are a well-known paradigm for complexity, as they generate robust dynamical macrostates and exhibit high levels of diversity, all based on simple rule sets. However, their quantum generalization has not previously been treated with the goal of physical (as opposed to computational) complexity in mind, and the correct time evolution schemes relevant to the non-local context of entangled quantum dynamics have not been established.
Exploring minimal extensions of classical elementary cellular automata to reversible quantum elementary cellular automata (QECA) couched in terms of realizable local unitary operations, we identify Goldilocks rules that not only exhibit robust dynamical features and diversity, but also complex network structure, a paradigm of complexity science from biosystems to social sciences. In the process, we identify a new set of complex quantum states that are highly entangled; thus QECA present a potential case for quantum speedup. Specifically, complex quantum states generated by Goldilocks QECA exhibit characteristic behaviors in their link density, clustering, and disparity when characterized by quantum-mutual-information-based complex networks, demonstrably distinct from random states. The time evolution of such states is characterized by highly structured dispersion relations. Particular rule sets exhibit soliton-like, yet entangled, emergent features with well-characterized transport properties.
References: Entangled quantum cellular automata: Logan Hillberry, Patrick Rall, David Vargas, Hannah North, Nicole Yunger Halpern, Ning Bao, Simone Montangero, Monika Schleier-Smith, and Lincoln D. Carr, “Complexity and Entanglement in Quantum Elementary Cellular Automata,” arXiv preprint to appear shortly (2017); G. K. Brennen and J. E. Williams, “Entanglement dynamics in one-dimensional quantum cellular automata,” Phys. Rev. A 68, 042311 (2003).
Quantum macroscopicity: Stefan Nimmrichter and Klaus Hornberger, Phys. Rev. Lett. 110, 160403 (2013); H. Jeong, M. Kang, and H. Kwon, "Characterizations and quantifications of macroscopic quantumness and its implementations using optical fields," Optics Communications 337, 12 (2015).
Quantum complex networks: David L. Vargas and Lincoln D. Carr, “Detecting Quantum Phase Transitions via Mutual Information Complex Networks,” Phys. Rev. Lett. under review (2016); Ed Bullmore and Olaf Sporns, “Complex brain networks: graph theoretical analysis of structural and functional systems,” Neuroscience 10, 186 (2009).
Quantum games of life: D. Bleh, T. Calarco, and S. Montangero, “Quantum Game of Life,” Europhys. Lett. 97, 20012 (2012); Pablo Arrighi and Jonathan Grattage, “The quantum game of life,” Physics World 25, 06 (2012).
To view the full schedule, please visit: http://physics.mines.edu/PH-physics-colloquia