To be announced
|May 19, 4pm||Andris Ambainis|
|June 23, 4pm||NN|
|July 28, 4pm||Toby Cubitt|
|September 15, 4pm||Peter Shor|
|October 13, 4pm||Umesh Vazirani|
|November 17, 4pm||Barbara Terhal|
|December 8, 4pm||Harry Buhrmann|
|January 19, 4pm||Robert Koenig|
|February 16, 5pm||Adam Bouland|
|February 11, 5pm||Thomas Vidick (Caltech)||Testing quantum systems in the high-complexity regime|
|July 22, 4pm||Andrew Childs (Maryland)||Efficient quantum algorithm for dissipative nonlinear differential equations|
|September 16, 4pm||Matthias Christandl (Copenhagen)||Fault-tolerant Coding for Quantum Communication|
|October 28, 2pm||Renato Renner( ETH )||Optimal universal programming of unitary gates|
|November 18, 2pm||Ashley Montanaro (Phasecraft and University of Bristol)||Observing ground-state properties of the Fermi-Hubbard model using a scalable algorithm on a quantum computer|
|December 16, 2pm||Aram Harrow (MIT)||Entanglement Spread in Communication Complexity and Many-Body Physics|
|February 17, 4pm||Stephanie Wehner (Delft)||Quantum Networks: From a Physics Experiment to a Quantum Network System|
Robert Koenig (TU Muenchen)
Thursday, January 19, 4pm.
We consider Kitaev's quantum double model based on a finite group G and describe quantum circuits for (a) preparation of the ground state, (b) creation of anyon pairs separated by an arbitrary distance, and (c) non-destructive topological charge measurement. We show that for any solvable group G all above tasks can be realized by constant-depth adaptive circuits with geometrically local unitary gates and mid-circuit measurements. Each gate may be chosen adaptively depending on previous measurement outcomes. Constant-depth circuits are well suited for implementation on a noisy hardware since it may be possible to execute the entire circuit within the qubit coherence time. Thus our results could facilitate an experimental study of exotic phases of matter with a non-abelian particle statistics. We also show that adaptiveness is essential for our circuit construction. Namely, task (b) cannot be realized by non-adaptive constant-depth local circuits for any non-abelian group G. This is in a sharp contrast with abelian anyons which can be created and moved over an arbitrary distance by a depth-1 circuit composed of generalized Pauli gates.
This is joint work with S. Bravyi, I. Kim and A. Kliesch, arXiv:2205.01933.
Harry Buhrmann (CWI and QuSoft)
One of the major challenges in computer science is to establish lower bounds on the resources, usually time, that are needed to solve computational problems. This holds in particular for computational problems that appear in practise.
One way towards dealing with this situation is the study of fine-grained complexity where we use special reductions to prove time lower bounds for many diverse problems based on the conjectured hardness of some key problems. For example, computing the edit distance between two strings, a problem that has a practical interest when determining the genetic distance between species based on their DNA, has an algorithm that takes O(n^2) time. Using a fine-grained reduction it can be shown that faster algorithms for edit distance also imply a faster algorithm for the Boolean Satisfiability (SAT) problem (that is believed to not exist). This is evidence that the current edit distance algorithms are optimal. Another problem, besides SAT, that is used as a basis for these reductions is the 3SUM problem.
The situation in the quantum regime is no better; almost all known lower bounds for quantum algorithms are defined in terms of query complexity, which doesn’t help much for problems for which the 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 for various reasons. In this talk, I will present some recent results in which we circumvent these challenges and prove quantum time lower bounds for some problems in BQP conditioned on the conjectured quantum hardness of for example SAT (and its variants) the 3SUM problem, and the All Pairs Shortest Path (APSP) problem.
One consequence of our work is that many computational problems have at most a quadratic quantum speedup and often even less. In practise, this speedup is countered by the slowdown quantum computers incur due to error-correction and fault tolerant computation, which means that for these tasks quantum advantage only kicks in for very large inputs. This in turn means that they require many logical qubits which will not be available in the foreseeable future.
This is based on joint work with Koen Leijnse, Bruno Loff, Subhasree Patro ,and Florian Speelman.
Quantum Error Correction Beyond Qubits
Barbara Terhal, Delft University
We review the formalism of stabilizer quantum error correction, in particular homological codes for qubits, oscillators or so-called rotors.
We show that rotors can in particular allow for interesting qubit encodings which relate to the physics of superconducting devices.
We discuss quantum error correction with the (homological) surface code, in particular with respect to qubit leakage, for superconducting qubits.
Umesh Vazirani, University of California at Berkeley
Google's 2019 experiment and their announcement of quantum supremacy relied on the inability of classical computers to efficiently carry out a task called random quantum circuit sampling (RCS). I will describe recent theoretical developments on the complexity of RCS. I will also describe a different line of work that provides scalable and rigorous proofs of quantumness based on an approach called the cryptographic leash, and the prospects of a concrete experimental challenge based on this approach.
Peter Shor, Department of Mathematics, MIT
Quantum money is a cryptographic protocol where one party (the mint) can prepare quantum states (each with a unique serial number) that can be verified but not duplicated. We sketch our 2010 quantum money protocol based on knot invariants and planar embeddings of knots, and sketch other proposals for quantum money that have been made since then, including our recent failed protocol.
Toby Cubitt, Professor of Quantum Information, Department of Computer Science., University College London
"Analogue" Hamiltonian simulation involves engineering a Hamiltonian of interest in the laboratory and studying its properties experimentally. Large-scale Hamiltonian simulation experiments have been carried out in optical lattices, ion traps and other systems for two decades. This is often touted as the most promising near-term application of quantum computing technology, as it is argued it does not require a scalable, fault-tolerant quantum computer.
Despite this, the theoretical basis for Hamiltonian simulation is surprisingly sparse. Even a precise definition of what it means to simulate a Hamiltonian was lacking. In my talk, I will explain how we put analogue Hamiltonian simulation on a rigorous theoretical footing, by drawing on techniques from Hamiltonian complexity theory in computer science, and Jordan and C* algebra results in mathematics.
I will then explain how this proved to be far more fruitful than a mere mathematical tidying-up exercise. It led to the discovery of universal quantum Hamiltonians [Science, 351:6 278, p.1180 (2016); Proc. Natl. Acad. Sci. 115:38 p.9497, (2018); J. Stat. Phys. 176:1 p228\u2013261 (2019); [[https://link.springer.com/article/10.1007/s00023-021-01111-7][Annales Henri Poincar?, 23 p.223 (2021)], later shown to have a deep connection back to quantum complexity theory [PRX Quantum 3:010308 (2022)]. The theory has also found applications in developing new and more efficient fermionic encodings for quantum computing [Phys. Rev. B 104:035118 (2021)], leading to dramatic reductions in the resource requirements for Hamiltonian simulation on near-term quantum computers [Nature Commun. 12:1, 4929 (2021)]. It has even found applications in quantum gravity, leading to the first toy models of AdS/CFT to encompass energy scales, dynamics, and (toy models of) black hole formation [J. High Energy Phys. 2019:17 (2019); J. High Energy Phys. 2022:52 (2022)].
Andris Ambainis: Quantum algorithms for search and optimization
Quantum algorithms are useful for a variety of problems in search and optimization. This line of work started with Grover's quantum search algorithm which achieved a quadratic speedup over naive exhaustive search but has now developed far beyond it.
In this talk, we describe three recent results in this area:
1. We show that, for any classical algorithm that uses a random walk to find an object with some property (by walking until the random walker reaches such an object), there is an almost quadratically faster quantum algorithm (https://arxiv.org/abs/1903.07493).
2. We show that the best known exponential time algorithms for solving several NP-complete problems (such as Travelling Salesman Problem or TSP) can be improved quantumly (https://arxiv.org/abs/1807.05209). For example, for the TSP, the best known classical algorithm needs time O(2^n) but our quantum algorithm solves the problem in time O(1.728...^n).
3. We show a almost quadratic quantum speedup for a number of geometric problems such as finding three points that are on the same line (https://arxiv.org/abs/2004.08949).
From carefully crafted quantum algorithms to information-theoretic security in cryptography, a quantum computer can achieve impressive feats with no classical analogue. Can their correct realization be verified? When the power of the device greatly surpasses that of the user, computationally as well as cryptographically, what means of control remain available to the user?
Recent lines of work in quantum cryptography and complexity develop approaches to this question based on the notion of an interactive proof. Generally speaking an interactive proof models any interaction whereby a powerful device aims to convince a restricted user of the validity of an agree-upon statementsuch as that the machine generates perfect random numbers or executes a specific quantum algorithm.
Two models have emerged in which large-scale verification has been shown possible: either by placing reasonable computational assumptions on the quantum device, or by requiring that it consists of isolated components across which Bell tests can be performed.
In the talk I will discuss recent results on the verification power of interactive proof systems between a quantum device and a classical user, focusing on the certification of quantum randomness from a single device (arXiv:1804.00640) and the verification of arbitrarily complex computations using two devices (arXiv:2001.04383).
Andrew Childs (University of Maryland): Efficient quantum algorithm for dissipative nonlinear differential equations.
While there has been extensive previous work on efficient quantum algorithms for linear differential equations, analogous progress for nonlinear differential equations has been severely limited due to the linearity of quantum mechanics. Despite this obstacle, we develop a quantum algorithm for initial value problems described by dissipative quadratic n-dimensional ordinary differential equations. Assuming R < 1, where R is a parameter characterizing the ratio of the nonlinearity to the linear dissipation, this algorithm has complexity T2 poly( log T, log n, log(1/ϵ) ) / ϵ, where T is the evolution time and ϵ is the allowed error in the output quantum state. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. We achieve this improvement using the method of Carleman linearization, for which we give a novel convergence theorem. This method maps a system of nonlinear differential equations to an infinite-dimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worst-case complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for R ≥ sqrt( 2 ). Finally, we discuss potential applications of this approach to problems arising in biology as well as in fluid and plasma dynamics.
Based on joint work with Jin-Peng Liu, Herman Kolden, Hari Krovi, Nuno Loureiro, and Konstantina Trivisa.
Designing encoding and decoding circuits to reliably send messages over many uses of a noisy channel is a central problem in communication theory. When studying the optimal transmission rates achievable with asymptotically vanishing error it is usually assumed that these circuits can be implemented using noise-free gates. While this assumption is satisfied for classical machines in many scenarios, it is not expected to be satisfied in the near term future for quantum machines where decoherence leads to faults in the quantum gates. As a result, fundamental questions regarding the practical relevance of quantum channel coding remain open. By combining techniques from fault-tolerant quantum computation with techniques from quantum communication, we initiate the study of these questions. As our main result, we prove threshold theorems for quantum communication, i.e. we show that coding near the (standard noiseless) classical or quantum capacity is possible when the gate error is below a threshold.
The recording is from an earlier presentation by Matthias at Harvard.
The “No-Programming Theorem” asserts that perfect universal quantum processors cannot exist. These are hypothetical devices that execute a unitary gate that is choosable arbitrarily and itself provided as a (quantum) input. This impossibility result depends however strongly on the requirement that the processor makes no errors. In my talk, I will present a recent robust version of the No-Programming Theorem. It basically answers the following question: Given a bound on the maximum tolerated error, what is the minimum size of the program that implements a unitary gate on a universal processor? As I shall explain, the answer to this question has an interesting connection to the Heisenberg limit of quantum metrology.
Ashley Montanaro (Phasecraft and University of Bristol): Observing ground-state properties of the Fermi-Hubbard model using a scalable algorithm on a quantum computer
The famous, yet unsolved, Fermi-Hubbard model for strongly-correlated electronic systems is a prominent target for quantum computers. However, accurately representing the Fermi-Hubbard ground state for large instances may be beyond the reach of near-term quantum hardware. In this talk I will discuss recent results showing experimentally that an efficient, low-depth variational quantum algorithm with few parameters can reproduce important qualitative features of medium-size instances of the Fermi-Hubbard model. We address 1x8 and 2x4 instances on 16 qubits on a superconducting quantum processor, substantially larger than previous work based on less scalable compression techniques, and going beyond the family of 1D Fermi-Hubbard instances, which are solvable classically. Consistent with predictions for the ground state, we observe the onset of the metal-insulator transition and Friedel oscillations in 1D, and antiferromagnetic order in both 1D and 2D. We use a variety of error-mitigation techniques, including symmetries of the Fermi-Hubbard model and a technique tailored to simulating fermionic systems. We also introduce a new variational optimisation algorithm based on iterative Bayesian updates of a local surrogate model. Our scalable approach is a first step to using near-term quantum computers to determine low-energy properties of strongly-correlated electronic systems that cannot be solved exactly by classical computers.
Aram Harrow (MIT)
Entanglement spread is an information-theoretic resource that (roughly) measures the gap between the highest and lowest Schmidt values of a pure bipartite quantum state. It turns out to characterize the communication cost needed to prepare the state starting from EPR pairs, as well as the cost of reflecting about the state. I will discuss the role of entanglement spread in two settings: communication complexity, and in the ground states of interacting quantum systems.
Stephanie Wehner (TU Delft)
(KM: The recording starts 2 minutes into the talk; I apologize.)
The internet has had a revolutionary impact on our world. The vision of a quantum internet is to provide fundamentally new internet technology by enabling quantum communication between any two points on Earth. Such a quantum internet can —in synergy with the “classical” internet that we have today—connect quantum information processors in order to achieve unparalleled capabilities that are provably impossible by using only classical information.
At present, such technology is under development in physics labs around the globe, but no large-scale quantum network systems exist. We start by providing a gentle introduction to quantum networks for computer scientists, and briefly review the state of the art. We highlight some of the many open questions to computer science in the domain of quantum networking, illustrated with a very recent result realizing the first quantum link layer protocol on a programmable 3 node quantum network based on Nitrogen-Vacancy Centers in Diamond.
We close by providing a series of pointers to learn more, as well as tools to download that allow play with simulated quantum networks without leaving your home.
Adam Bouland (Stanford)
Quantum pseudorandom states are efficiently constructable states which nevertheless masquerade as Haar-random states to poly-time observers. First defined by Ji, Liu and Song, such states have found a number of applications ranging from cryptography to the AdS/CFT correspondence. A fundamental question is exactly how much entanglement is required to create such states. Haar-random states, as well as t-designs for t≥2, exhibit near-maximal entanglement. Here we provide the first construction of pseudorandom states with only polylogarithmic entanglement entropy across an equipartition of the qubits, which is the minimum possible. Our construction can be based on any one-way function secure against quantum attack. We additionally show that the entanglement in our construction is fully "tunable", in the sense that one can have pseudorandom states with entanglement Θ(f(n)) for any desired function ω(logn)≤f(n)≤O(n). More fundamentally, our work calls into question to what extent entanglement is a "feelable" quantity of quantum systems. Inspired by recent work of Gheorghiu and Hoban, we define a new notion which we call "pseudoentanglement", which are ensembles of efficiently constructable quantum states which hide their entanglement entropy. We show such states exist in the strongest form possible while simultaneously being pseudorandom states. We also describe diverse applications of our result from entanglement distillation to property testing to quantum gravity.
Based on joint work with Bill Fefferman, Soumik Ghosh, Umesh Vazirani, and Zixin Zhou, arXiv:2211.00747