Monday, October 17
QNC 0101
| 9:45 pm | Welcome by Christine Muschik and William Slofstra |
| 9:50 am | Opening remarks by IQC Director Norbert Lütkenhaus |
| 10:00 am |
Alex Dalzell, Amazon Web Services, Center for Quantum Computing Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end |
| 10:45 am | Break |
| 11:15 am |
Armanda O. Quintavalle, University of Sheffield Hypergraph product codes:a bridge to scalable quantum computers |
| 12:00 pm | Lunch |
| 1:00 pm | |
| 1:45 pm | Break |
| 2:15 pm | |
| 3:00 pm | |
| 3:45 pm | Quantum Innovators speakers and IQC faculty members are invited to a private reception in QNC 2101 |
Tuesday, October 18
QNC 0101
| 9:15 am | |
| 10:00 am | |
| 10:45 am | Break |
| 11:15 am | |
| 12:00 pm | Lunch |
| 1:00 pm |
Ewin Tang, University of Washington Query-optimal estimation of unitary channels in diamond distance |
| 1:45 pm | Break |
| 2:15 pm |
Flaminia Giacomini, Perimeter Institute for Theoretical Physics Quantum mechanics and the covariance of physical laws in quantum reference frames |
| 3:00 pm | |
| 3:45 pm | Break |
| 4:15 pm | |
| 5:00 pm |
Tony Leggett, University of Illinois at Urbana-Champaign Some remarks concerning Majorana fermions in 2D (p+ip) Fermi superfluids |
Wednesday, October 19
QNC 0101
| 10:00 am |
Meenu Kumari, Perimeter Institute Eigenstate entanglement in integrable collective spin models |
| 10:45 am | Break |
| 11:15 am |
Anthony (Chi Fang) Chen, California Institute of Technology Worst-case and average-case separation in quantum simulation and quantum dynamics |
| 12:00 pm | Lunch |
| 1:00 pm |
Mehdi Soleimanifar, California Institute of Technology New features of interacting quantum systems and their algorithmic applications |
| 1:45 pm | |
| 2:30 pm |
Closing remarks |
Ulysse Chabaud, California Institute of Technology
Stellar representation of quantum computations
We study the stellar representation of quantum computations, based on holomorphic functions, which delineates the boundary between discrete-and continuous-variable quantum information theory. This representation provides an elegant characterization of non-Gaussian quantum states that are resourceful for bosonic quantum computing: in the single-mode case, the evolution of a single bosonic mode under a Gaussian Hamiltonian can be described using a dynamical system of classical particles corresponding to the non-Gaussian zeros of the holomorphic function; in the multimode case, this holomorphic representation also induces a faithful and robust non-Gaussian hierarchy of quantum states. From this representation, we obtain a classification of subuniversal bosonic models that are generalisations of Boson Sampling and Gaussian quantum computing. arXiv:2111.00117, joint work with Saeed Mehraban.
Anthony (Chi Fang) Chen, California Institute of Technology
Worst-case and average-case separation in quantum simulation and quantum dynamics
Physical Hamiltonians are often a sum over k-body (k-local) terms. In this talk, we draw connections between this locality and the ubiquitous separation between worst-case and average-case properties. We present two examples: quantum simulation using product formula enjoys an average-case v.s worst-case speedup; quantum dynamics in power-law interacting systems is qualitatively different for the finely-tuned states and the typical states. The main technical framework uses "uniform smoothness" for matrix martingales to exploit the k-locality structure. His research is supported by the Eddleman Fellowship.
Alex Dalzell, Amazon Web Services, Center for Quantum Computing
Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
I present a simple quantum algorithm for solving binary optimization problems. The algorithm finds the exactly optimal solution to the optimization problem in time that we prove is upper bounded by O∗(2(0.5−c)n) for an n-independent constant c, a 2cn advantage over Grover’s algorithm. The algorithm and its analysis is largely inspired by (but distinct from) Hastings’ short-path algorithm [Quantum 2, 78 (2018)].
Based on joint work with Nicola Pancotti, Earl Campbell, and Fernando Brandão.
Di Fang, University of California, Berkeley
Time-dependent Hamiltonian simulation of highly oscillatory dynamics and super convergence for Schrödinger equation
Recent years have witnessed tremendous progress in developing and analyzing quantum algorithms for quantum dynamics simulation (Hamiltonian simulation). The difficulty of the task increases as the underlying dynamics becomes highly oscillatory – when the Hamiltonian has a large operator norm and/or varies rapidly. We propose a simple quantum algorithm for simulating highly oscillatory quantum dynamics, which does not require complicated quantum control logic for handling time-ordering operators. To our knowledge, this is the first quantum algorithm that is both insensitive to the rapid changes of the time-dependent Hamiltonian and exhibits com-mutator scaling. The algorithm can be viewed as a generalization of the first and second order Trotter formulae. Interestingly, our method exhibits superconvergence in the digital simulation of the Schrödinger equation with unbounded operators.
Flaminia Giacomini, Perimeter Institute for Theoretical Physics
Quantum mechanics and the covariance of physical laws in quantum reference frames
In physics, observations are typically made with respect to a frame of reference. Although reference frames are usually not considered as degrees of freedom, in practical situations it is a physical system which constitutes a reference frame. Can a quantum system be considered as a reference frame and, if so, which description would it give of the world? In the talk, I will introduce a general method to associate a reference frame to a quantum system, which generalises the usual reference frame transformation to a "superposition of coordinate transformations”. Such quantum reference frames transformations imply that the notion of entanglement and superposition are not given a priori, but depend on the choice of the quantum reference frame even in a non-relativistic setting. I will additionally show how quantum reference frames allow one to generalise the weak equivalence principle.
Dominik Hangleiter, University of Maryland
Assessing analog quantum simulators
Analog quantum simulators allows us to solve problems efficiently that are intractable to solve using classical computers. Today, we are at an exciting point in time: Highly accurate analog quantum simulators exist in laboratories around the world. But how good and how powerful are those devices? In this talk, I approach this question from various perspectives. Starting from acomputational-complexity perspective, I present a proof showing that very simple analog dynamics can provide a quantum speedup. Then, I take on a practical point of view, and discuss the problem of verifying and characterizing analog quantum simulators in practice. Specifically, I will show a diagnostic toolkit that comprises a randomized bench marking protocol forbosonic dynamics and a protocol for identifying the Hamiltonian of such a system. I close by showing how to run this protocol in practice on up to 14 qubits in a superconducting qubit architecture.
Robert Huang, California Institute of Technology
Learning and making predictions in a quantum world
Many scientific advancements in physics and chemistry depend on our ability to learn and make predictions in a quantum world. The talk covers recent results in understanding the power of classical and quantum machine learning (ML)algorithms. We begin by presenting efficient classical ML algorithms for predicting ground state properties in quantum many-body systems that cannot be efficiently solved by any classical algorithms assuming a widely-accepted complexity-theoretic conjecture. This result demonstrates the advantage of classical ML algorithms over classical algorithms. After examining the capability of classical ML, we study the power of quantum ML. We prove that, in various tasks, quantum machines could learn from exponentially fewer experiments than those required by their classical counterparts. Conducting experiments with up to 40 superconducting qubits and 1300 quantum gates, we demonstrate that a substantial quantum advantage can be realized using today's relatively noisy quantum processors.
Zahra Khanian, Technical University of Munich
Strong converse bounds for compression of mixed states
The optimal rates for compression of mixed quantum states was found by Koashi and Imotoin 2001 for the blind case and by Horodecki and independently by Hayashi for the visible case respectively in 2000 and 2006. However, it was not known so far whether the strong converse property holds for these compression problems. In this work, we show that the strong converse holds for the blind compression scheme. For the visible scheme, the strong converse holds up to the continuity of the regularised Rényi entanglement of purification.
William Kretschmer, University of Texas at Austin
Quantum Cryptography in Algorithmica
In this talk, I will discuss a construction of a classical oracle relative to which pseudorandom quantum states exist and yet P=NP. This shows that, even though classical one-way functions are sufficient to construct pseudorandom states, they are not at all necessary, at least in the black box setting. Our proof builds on recent work of Aaronson, Ingram, and Kretschmer (2022). Based on joint work with Luowen Qian, Makrand Sinha, and Avishay Tal.
Meenu Kumari, Perimeter Institute
Eigenstate entanglement in integrable collective spin models
The characterization of integrability and chaos in quantum mechanics is a long-standing open problem. Entanglement is a strong candidate for this characterization but exactly how remains debatable. The average entanglement entropy (EE) of the energy eigenstates in non-vanishing partitions has been recently proposed as a diagnostic of integrability in quantum many-body systems. For it to be a faithful characterization of quantum integrability, it should distinguish quantum systems with a well-defined classical limit in the same way as the unequivocal classical integrability criteria. We examine the proposed diagnostic in the class of collective spin models characterized by permutation symmetry in the spins. The well-known Lipkin-Meshov-Glick (LMG) model is a paradigmatic integrable system in this class with a well-defined classical limit. Thus, this model is an excellent testbed for examining quantum integrability diagnostics. First, we calculate analytically the average EE of the Dicke basis in any non-vanishing bipartition, and show that in the thermodynamic limit, it converges to 1/2 of the maximal EE in the corresponding bipartition. Using finite-size scaling, we numerically demonstrate that the aforementioned average EE in the thermodynamic limit is universal for all parameter values of the LMG model. Our analysis illustrates how the value of the average EE in the thermodynamic limit may be a robust criterion for identifying integrability.
Murphy Yuezhen Niu, Google Quantum
Learning quantum systems via out-of-time-ordered correlators
Learning the properties of dynamical quantum systems underlies applications ranging from nuclear magnetic resonance spectroscopy to quantum device characterization. A central challenge in this pursuit is the learning of strongly-interacting systems, where conventional observables decay quickly in both time and space, limiting the information that can be learned from their measurement. In this work, we introduce a new class of observables into the context of quantum learning—the out-of-time-ordered correlators—which we show can substantially improve the learnability of strongly-interacting systems by virtue of displaying informative physics at large times and distances. We identify two general scenarios in which out-of-time-ordered correlators provide a significant advantage for learning tasks in local Hamiltonian systems for which (i) when experimental access to the system is spatially-restricted, for example via a single“probe” degree of freedom, and (ii) for detecting weak interactions, whose strength is much less than the typical interaction strength and which thus manifest only at late times. We numerically characterize these advantages across a variety of learning problems, and find that they are robust to both read-out error and decoherence. Finally, we introduce a binary classification task involving Haar-random unitaries that can be accomplished in constant time with out-of-time-ordered measurements. In a companion paper [1], we prove that this task is exponentially hard with any adaptive learning protocol that only involves time-ordered operations.
Subhasree Patro, Centrum Wiskunde & Informatica
Quantum Fine-Grained Complexity
One of the major challenges in the field of complexity theory is the inability to prove unconditional time lower bounds. One way around this is the study of fine-grained complexity where we use special reductions to prove time lower bounds for many problems in complexity class P based on the conjectured hardness of some key problems like the Satisfiability (SAT) problem, 3SUM or APSP. The situation in the quantum regime is no better; almost all known lower bounds are defined in terms of query complexity, which is not very useful for problems whose best-known algorithms take super linear time. Therefore, employing fine-grained reductions in the quantum setting seems a natural way forward. However, translating the classical fine-grained reductions directly into the quantum regime is not always possible. In this talk, I will present some results in which we prove quantum time lower bounds for some problems in BQP conditioned on the conjectured quantum hardness of SAT (and its variants), 3SUM and APSP.
Armanda O. Quintavalle, University of Sheffield
Hypergraph product codes:a bridge to scalable quantum computers
Hypergraph product codes are a generalization of the planar code that can store multiple logical qubits. As such, they could provide a low(er) overhead alternative to topological codes for fault-tolerant quantum computer architectures. For this alternative to be viable, it is essential to find both efficient decoders and fault-tolerant schemes for logical gates.In this talk, we address both of these issues. We propose the first example of an optima alminimum-weight decoder that works for all families of hypergraph product codes. Second, we describe how the symmetries of two-dimensional hypergraph product codes can be leveraged to perform logical Clifford operations fault-tolerantly. Our scheme can be augmented with state injection and techniques from pieceable fault tolerance to allow universal computation.
Mehdi Soleimanifar, California Institute of Technology
New features of interacting quantum systems and their algorithmic applications
In this talk, I will discuss new features of interacting quantum systems through the lens of computational complexity and information theory. We will see how using these new features in turn allows us to develop efficient algorithms for learning and simulating quantum many-body systems.
Ewin Tang, University of Washington
Query-optimal estimation of unitary channels in diamond distance
We will present an algorithm to learn an unknown unitary channel acting on a d-dimensional qudit to diamond-norm error ε, using O(d²/ε) applications of the unknown channel and only one qudit. This algorithm uses the optimal number of qudits and number of queries up to a sub-logarithmic factor, even if one has access to the inverse or controlled versions of the unknown unitary. This improves over prior work, which achieves entanglement infidelity δ using O(d²/√δ) applications in parallel, thereby requiring Ω(d²) qudits. Based on joint work with Jeongwan Haah, Robin Kothari, and Ryan O'Donnell.
Kianna Wan, Stanford University
Matchgate Shadows for Fermionic Quantum Simulation
In this talk, I'll describe new tomographic protocols for efficiently estimating various fermionic quantities, including both local observables (i.e., expectation values of local fermionic operators) and certain global properties (e.g., inner products between an unknown quantum state and arbitrary fermionic Gaussian states). Our protocols are based on classical shadows arising from random matchgate circuits, and as a concrete application, they enable us to apply wavefunction constraints that control the fermion sign problem in the recently introduced quantum-classical quantum Monte Carlo algorithm, without the exponential post-processing cost incurred by the original approach.
James Watson, University of Maryland
The Complexity of Quantum Phase Transitions
The phase diagram of a material is of central importance in describing the properties and behaviour of a condensed matter system. Indeed, the study of quantum phase transitions has formed a central part of 20th and 21st Century physics. We examine the complexity and computability of determining the phase diagram of a general Hamiltonian. We show that in the worst case it is uncomputable and in more restricted cases, where the Hamiltonian is “better behaved”, it remains computationally intractable even for a quantum computer.