Research
Interests
I am mainly interested in applying tools from quantum information to apply to other areas of physics, such as condensed matter and manybody physics of atomic, molecular and optical systems. A major theme of my research is that of computational complexity theory, and what statements we can make about physical systems using complexity theory.
Publications
You can find my publications on Google Scholar, arXiv, or on ORCID. They are also listed here in reverse chronological order.

Sharp complexity phase transitions generated by entanglement, arXiv:2212.10582
(with Soumik Ghosh, Dominik Hangleiter, Alexey V. Gorshkov and Bill Fefferman)
Entanglement is necessary, but not always sufficient, for the classical hardness of simulating quantum dynamics. But how much entanglement is needed in general? A quantitative link is missing. Here, we study a family of states, kregular graph states, and show that both the entanglement and complexity of this class of states are linked. They display transitions as a function of k at the same points. Far from being a coincidence, the entanglement transition can be said to cause the complexity transition. 
Page curves and typical entanglement in linear optics, arXiv:2209.06838
(with Joseph T. Iosue, Adam Ehrenberg, Dominik Hangleiter, and Alexey V. Gorshkov)
In this work, we derive the bosonic analogue of the Page curve for qudits, namely the average entanglement as a function of subsystem size for a family of random Gaussian states. We also obtain typicality results for the entanglement. The states considered are precisely those that are outputs of Gaussian Boson Sampling (GBS) experiments. 
Quantuminspired permanent identities, Quantum 6, 877 (2022), arXiv:2208.00327
(with Ulysse Chabaud and Saeed Mehraban)
The permanent is a fascinating mathematical object that appears very naturally in linear optics. The permanent vs. the determinant dichotomy is also related to the boson vs. fermion dichotomy in physics. In this work, we build on this connection with linear optics to derive several identities for the permanent, some previously known and some unknown. These include generalisations of the MacMahon master theorem, an identity relating the permanent to the determinant. We also obtain new results for the hardness of simulating linear optics with cat states as input. 
Simulation Complexity of ManyBody Localized Systems, arXiv:2205.12967
(with Adam Ehrenberg, Christopher Baldwin, Dmitry Abanin, and Alexey Gorshkov
Localised systems are believed to be generally “simpler” than typical, generic condensedmatter systems. Can this “simplicity” be quantified mathematically? In this work, we rigorously show that manybodylocalised (MBL) systems are easier to simulate than generic, chaotic systems. This is shown in two senses: the classical easiness/hardness of simulating time evolution under MBL Hamiltonians, and the quantum gate complexity of Hamiltonian time evolution. The latter shows a sublinear growth, which forms a nice counterpart to a recent result that showed a linear growth of exact circuit complexity. 
Monitoringinduced Entanglement Entropy and Sampling Complexity, Physical Review Research 4, L032021 (2022), arXiv:2201.12672
(with Mathias Van Regemortel, Oles Shtanko, Luis Pedro GarciaPintos, Hossein Dehghani, Alexey Gorshkov, and Mohammad Hafezi)
We looked at a simple system of emitters described by a master equation and considered different unravellings of the same underlying master equation. The different unravellings correspond to different ways of monitoring emitted photons. These unravellings differ with respect to the entanglement they generate. There is a direct relation between the entanglement generated and the complexity of the monitoring scheme, a.k.a. the complexity of the linear optical network through which the photons pass before being measured. 
Tight bounds on the convergence of noisy random circuits to the uniform distribution, PRX Quantum 3, 040329 (2022), arXiv:2112.00716
(with Pradeep Niroula, Oles Shtanko, Alexey Gorshkov, Bill Fefferman, and Michael Gullans)
In this work, we considered how fast noisy random circuits converge to the uniform distribution. We prove that for an $n$qubit system evolving under Haarrandom local gates for depth $d$ and subject to local Pauli noise, the average total variation distance from the uniform distribution scales as $\delta \sim \exp[\tilde{\Theta}(d)]$. This has implications for proof techniques purporting to show a quantum computational advantage via approximate sampling. 
Quantum Computational Advantage via HighDimensional Gaussian Boson Sampling, Science Advances 8, eabi7894 (2022), arXiv:2102.12474
(with Arthur Mehta, Trevor Vincent, Nicolas Quesada, Marcel Hinsche, Marios Ioannou, Lars Madsen, Jonathan Lavoie, Haoyu Qi, Jens Eisert, Dominik Hangleiter, Bill Fefferman, and Ish Dhand)
In this paper, we propose a new architecture we call highdimensional Gaussian Boson Sampling. We show that this architecture has many of the hardness properties shared by other schemes (such as random circuit sampling) for exhibiting a quantum computational advantage over classical computers. Along the way, we also give improved evidence for the asymptotic hardness of the original Gaussian Boson Sampling proposal. We also give concrete estimates of the classical cost of simulating a finitesize experiment using known algorithms. 
Optimal state transfer and entanglement generation in powerlaw interacting systems, Physical Review X 11, 031016 (2021), arXiv:2010.02930
(with Minh Tran, Andrew Guo, Andrew Lucas, and Alexey Gorshkov)
In this work, we give a new optimal protocol for transferring an unknown state from one site in a $d$dimensional lattice from one end to another with powerlaw interactions with powerlaw exponent $\alpha$. The protocol proceeds via generation of largescale entangled states, like the GHZ state. In some regimes (when $\alpha \in (d,2d]$), the protocol achieves an exponential speedup compared to the previously existing protocols. 
The importance of the spectral gap in estimating groundstate energies, PRX Quantum 3, 040327 (2022), arXiv:2007.11582
(with Alexey Gorshkov and Bill Fefferman)
In this work, we study how the spectral gap affects the complexity of a variant of the “Local Hamiltonian” problem, namely that of computing the groundstate energy of a local Hamiltonian to inverseexponential precision. We give strong complexitytheoretic evidence that a nontrivial spectral gap makes the problem easier. Our findings might also have implications for the circuit complexity of ground states of local Hamiltonians. 
Implementing a Fast Unbounded Quantum Fanout Gate Using PowerLaw Interactions, Physical Review Research 4, L042016, arXiv:2007.00662
(with Andrew Guo, SuKuan Chu, Zachary Eldredge, Przemyslaw Bienias, Dhruv Devulapalli, Yuan Su, Andrew Childs, and Alexey Gorshkov)
In this work, we give a way of implementing fast fanout gates that take time at most logarithmic in the system size in a system with powerlaw interactions. We also devise a new technique based on the Frobeniusnorm lightcone developed in arXiv:2001.11509 (paper #9 below) to lowerbound the time required to build the fanout and QFT gates. 
Limits on Classical Simulation of Free Fermions with Dissipation, PRX Quantum 2, 030350, arXiv:2005.10840
(with Oles Shtanko, Paul Julienne, and Alexey Gorshkov)
This work deals with classical simulability of fermionic open systems with quadratic Hamiltonians and quadraticlinear Lindblad operators (corresponding to quartic terms in the Liouvillian). We classify the set of Lindblad operators based on whether they give rise to simulable dynamics or lead to dynamics that are equivalent in computational power to universal quantum computation. This also suggests a scheme for quantum computing with fermionic atoms coupled to an environment. 
Hierarchy of linear light cones with longrange interactions, Physical Review X, 10, 031009 (2020), arXiv:2001.11509
(with Minh Tran, ChiFang Chen, Adam Ehrenberg, Andrew Guo, Yifan Hong, ZheXuan Gong, Alexey Gorshkov, and Andrew Lucas)
In this paper, we show that for longrange interacting systems, i.e. those where interactions decay with distance as a power law, the standard technique of showing a LiebRobinson bound only captures a “worstcase” speed limit of spreading of quantum correlations. We show that processes like state transfer and quantum scrambling are instead governed by tighter speed limits that better capture typical, or “averagecase”, behaviour. We also show the tightness of recently obtained linear lightcones.
Also see coverage here: A Speed Test for Ripples in a Quantum System and New Quantum Information Speed Limits Depend on the Task at Hand 
Entanglement Bounds on the Performance of Quantum Computing Architectures, Physical Review Research 2, 033316 (2020), arXiv:1908.04802
(with Zachary Eldredge, Leo Zhou, Aniruddha Bapat, James Garrison, Frederic Chong, and Alexey Gorshkov)
This work has the same motivation as arXiv:1808.07876, where we evaluate graphs that prescribe how to wire up different modules of a quantum computer. We deal with the more general case of measurements and feedback here and show a lower bound on the time required to create highlyentangled states on graphs. We also show that this bound can be saturated up to a logarithmic factor in the number of qubits. 
Complexity phase diagram for interacting and longrange bosonic Hamiltonians, Physical Review Letters 129, 150604 (2022), arXiv:1906.04178
(with Nishad Maskara, Adam Ehrenberg, Minh Tran, Bill Fefferman, and Alexey Gorshkov)
This work is in the same vein as arXiv:1703.05332 (paper #3 below). We classify a family of bosonic Hamiltonians based on the complexity of simulating its time evolution on a classical computer and draw a “complexity phase diagram” for the system, a slice of which is shown in the paper. This illustrates how computational complexity theory may have something to say about phases in manybody physics. We also see two different types of transitions, which suggests the presence of a rich variety of complexity phase diagrams. 
Quantum Approximate Optimization with a TrappedIon Quantum Simulator, Proceedings of the National Academy of Sciences, 202006373, arXiv:1906.02700
(with Guido Pagano, Aniruddha Bapat, Patrick Becker, Katherine Collins, Arinjoy De, Paul Hess, Harvey Kaplan, Antonis Kyprianidis, WenLin Tan, Christopher Baldwin, Lucas Brady, Fangli Liu, Stephen Jordan, Alexey Gorshkov, and Christopher Monroe)
This work experimentally demonstrates a quantum approximate optimisation algorithm (QAOA) on an ion trap to find the ground state energy of the longrange transversefield Ising model. On the theory side, we supplement this study with observations on how the optimal parameters in the algorithm behave with increasing system size and depth, and an extension of Farhi and Harrow’s proof of exact sampling hardness to the approximate case. 
Interference of Temporally Distinguishable Photons Using FrequencyResolved Detection, Physical Review Letters 123, 123603 (2019), arXiv:1904.03222
(with Venkata Vikram Orre, Elizabeth Goldschmidt, Alexey Gorshkov, Vincenzo Tamma, Mohammad Hafezi, and Sunil Mittal)
In this experimental work, we demonstrate the interference of two and three a priori distinguishable photons by stretching the photons in time to remove their distinguishability. We also give a theoretical outline of why a scaledup version of this setup may be hard to simulate on a classical computer.
Also see coverage here: Stretched Photons Recover Lost Interference. 
Unitary Entanglement Construction in Hierarchical Networks, Physical Review A 98, 062328 (2018), arXiv:1808.07876
(with Aniruddha Bapat, Zachary Eldredge, James Garrison, Frederic Chong, and Alexey Gorshkov)
In this paper, we examine the tradeoff between speed and cost when deciding how to wire together different modules of a quantum computer. We give a class of networks called “hierarchical networks” and show that they have favourable properties for creating large entangled states. The ease of describing these networks also leads to good strategies for deciding how to map algorithm qubits to machine qubits. 
Dynamical phase transitions in sampling complexity, Physical Review Letters 121, 030501 (2018), arXiv:1703.05332
(with Bill Fefferman, Minh Tran, Michael FossFeig, and Alexey Gorshkov)
In this paper, we argue that studying quantum advantage is useful in other areas of physics too namely to delineate phases and identify phase transitions in manybody physics. This is because complexity theory inherently gives us a way of classifying systems into “easy” or “hard” (to simulate on a classical computer), and classification is ubiquitous in physics.
Also see coverage here: Complexity test offers new perspective on small quantum computers. 
Lattice Laughlin states on the torus from conformal field theory, Journal of Statistical Mechanics: Theory and Experiment 2016 (1), 013102, arXiv:1507.04335
(with Anne Nielsen)
Here we derive the analogue of Laughlin wavefunctions for lattices with periodic boundary conditions, and derive various properties of these states, such as the modular Smatrix (which describes the phases picked up by anyons upon braiding them around each other). 
Remote tomography and entanglement swapping via von Neumann–Arthurs–Kelly interaction, Physical Review A 89, 052107 (2014), arXiv:1308.2852
(with S. M. Roy and Nitica Sakharwade)
In this paper, we give a method to perform remote tomography on a particle (say, a photon) without sending or teleporting it directly. In order to transmit information about the particle of interest, we use a “von NeumannArthursKelly interaction” between the particle and two other particles that are more amenable to longdistance transmission over telecom wavelengths.