I am mainly interested in applying tools from quantum information to apply to other areas of physics, such as condensed matter and many-body 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.


You can find my publications on Google Scholar, arXiv, or on ORCID. They are also listed here in reverse chronological order.

  1. A sharp phase transition in linear cross-entropy benchmarking, arXiv:2305.04954

    (with Brayden Ware, Dominik Hangleiter, Pradeep Niroula, Bill Fefferman, Alexey V. Gorshkov, and Michael Gullans)
    The linear cross-entropy benchmark (XEB) is a popular measure used to estimate the fidelity of a random quantum circuit subject to noise. Recent work has showed that in an $n$-qubit circuit, the XEB approximates the fidelity well in certain regimes of noise strengths, namely if the noise strength per qubit is $\epsilon \ll 1/n$. In this work, we show that as the noise strength increases, the correspondence between the fidelity and the XEB breaks down sharply at a critical value of the noise strength. This critical value depends on the geometry of the random circuit architecture and the choice of gate set.

  2. 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, k-regular 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.

  3. Page curves and typical entanglement in linear optics, Quantum 7, 1017 (2023), 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.

  4. Quantum-inspired 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.

  5. Simulation Complexity of Many-Body 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 condensed-matter systems. Can this “simplicity” be quantified mathematically? In this work, we rigorously show that many-body-localised (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.

  6. Monitoring-induced Entanglement Entropy and Sampling Complexity, Physical Review Research 4, L032021 (2022), arXiv:2201.12672

    (with Mathias Van Regemortel, Oles Shtanko, Luis Pedro Garcia-Pintos, 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.

  7. 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 Haar-random 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.

  8. Quantum Computational Advantage via High-Dimensional 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 high-dimensional 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 finite-size experiment using known algorithms.

  9. Optimal state transfer and entanglement generation in power-law 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 power-law interactions with power-law exponent $\alpha$. The protocol proceeds via generation of large-scale 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.

  10. The importance of the spectral gap in estimating ground-state 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 ground-state energy of a local Hamiltonian to inverse-exponential precision. We give strong complexity-theoretic 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.

  11. Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions, Physical Review Research 4, L042016, arXiv:2007.00662

    (with Andrew Guo, Su-Kuan 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 power-law interactions. We also devise a new technique based on the Frobenius-norm light-cone developed in arXiv:2001.11509 (paper #9 below) to lower-bound the time required to build the fanout and QFT gates.

  12. 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 quadratic-linear 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.

  13. Hierarchy of linear light cones with long-range interactions, Physical Review X, 10, 031009 (2020), arXiv:2001.11509

    (with Minh Tran, Chi-Fang Chen, Adam Ehrenberg, Andrew Guo, Yifan Hong, Zhe-Xuan Gong, Alexey Gorshkov, and Andrew Lucas)
    In this paper, we show that for long-range interacting systems, i.e. those where interactions decay with distance as a power law, the standard technique of showing a Lieb-Robinson bound only captures a “worst-case” 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 “average-case”, behaviour. We also show the tightness of recently obtained linear light-cones.
    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

  14. 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 highly-entangled states on graphs. We also show that this bound can be saturated up to a logarithmic factor in the number of qubits.

  15. Complexity phase diagram for interacting and long-range 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 many-body physics. We also see two different types of transitions, which suggests the presence of a rich variety of complexity phase diagrams.

  16. Quantum Approximate Optimization with a Trapped-Ion 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, Wen-Lin 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 long-range transverse-field 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.

  17. Interference of Temporally Distinguishable Photons Using Frequency-Resolved 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 scaled-up version of this setup may be hard to simulate on a classical computer.
    Also see coverage here: Stretched Photons Recover Lost Interference.

  18. 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.

  19. Dynamical phase transitions in sampling complexity, Physical Review Letters 121, 030501 (2018), arXiv:1703.05332

    (with Bill Fefferman, Minh Tran, Michael Foss-Feig, 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 many-body 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.

  20. 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 S-matrix (which describes the phases picked up by anyons upon braiding them around each other).

  21. 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 Neumann-Arthurs-Kelly interaction” between the particle and two other particles that are more amenable to long-distance transmission over telecom wavelengths.