# Schedule for: 22w5111 - Probability and Quantum Information Science (Online)

Beginning on Sunday, March 13 and ending Friday March 18, 2022

All times in Banff, Alberta time, MST (UTC-7).

Monday, March 14 | |
---|---|

09:00 - 09:10 | Jeffrey Schenker: Welcome and Overview (Online) |

09:10 - 10:10 |
Mario Szegedy: Quantum random circuits and the averaging process ↓ Google supremacy experiments have raised new statistical questions about random
quantum circuits. After presenting some of these, we delve into questions related to a
particular random process, the so-called averaging process, which is studied at least from
the 80s. Recently Sourav Chatterjee, Persi Diaconis, Allan Sly and Lingfu Zhang have
established a sharp convergence cutoff of
\( 1/(2 * \log 2) * n * \log n + O(n * \sqrt(\log n)) \)
when
we run the process on the complete graph. We prove that the complete graph is an extreme
case: we cannot get a quicker convergence on any other graph. We also resolve a conjecture
of Sam Spiro: the convergence in the case of the the cycle graph occurs in time \( \Theta(n^3) \).
We also make several other observations about the process. Joint with Ramis Movassagh and
Guanyang Wang. (Online) |

12:00 - 13:00 |
Nicole Yunger Halpern: Linear growth of quantum circuit complexity ↓ Quantifying quantum states' complexity is a key problem in various
subfields of science, from quantum computing to black-hole physics. We
prove a prominent conjecture by Brown and Susskind about how random
quantum circuits' complexity increases. Consider constructing a unitary
from Haar-random two-qubit quantum gates. Implementing the unitary
exactly requires a circuit of some minimal number of gates—the unitary's
exact circuit complexity. We prove that this complexity grows linearly with
the number of random gates, with unit probability, until saturating after
exponentially many random gates. Our proof is surprisingly short, given the
established difficulty of lower-bounding the exact circuit complexity. Our
strategy combines differential topology and elementary algebraic geometry
with an inductive construction of Clifford circuits.
References
1) Haferkamp, Faist, Kothakonda, Eisert, and NY H, accepted by Nat. Phys.
(in press) arXiv:2106.05305.
2) NY H, Kothakonda, Haferkamp, Munson, Faist, and Eisert,
arXiv:2110.11371 (2021). (Online) |

13:10 - 14:10 |
Ilya Kachkovskiy: Quasiperiodic operators with monotone potentials and Anderson localization ↓ For single-particle quantum systems described by Schrödinger operators, Anderson localization is a
phenomenon of having dense purely point spectrum with exponentially decaying eigenfunctions. One
can relate is with absence of transport and presence of disorder, such as random disorder in the
Anderson model. In the one-dimensional case, the tight binding Anderson model demonstrates
localization regardless of the strength of the coupling at the disorder term. In 1980s, it was discovered
that models with ergodic non-random disorder, such as quasiperiodic operators, demonstrate Anderson
localization at large coupling. However, the case of small coupling for analytic quasiperiodic operators is
very different and one can show the presence of absolute continuous spectrum and transport.
In the present talk, I will focus on a large class of quasiperiodic operators with monotone or locally
monotone potentials which, under relatively mild regularity conditions, have much stronger localization
properties than those with analytic potentials. In particular, one can obtain localization at small coupling
in ID, such as in random models, and uniform localization that does not appear in other models, which
allows to argue that these operators demonstrate more "random-like" behavior than analytic
quasiperiodic operators. In some regimes, one can prove localization by directly constructing converging
perturbation series for eigenvalues and eigenvectors, while in other regimes the methods are very
indirect. (Online) |

14:10 - 15:00 | Informal Discussion (Online) |

Tuesday, March 15 | |
---|---|

09:00 - 10:00 |
Vladimir Korepin: Quantum search on noisy intermediate-scale quantum devices. ↓ The Quantum search algorithm (also known as Grover's algorithm) lays the foundation of many other quantum algorithms. It demonstrates an advantage (for unstructured search) over the classical algorithm. Although it is very simple, its implementation is limited on the noisy intermediate-scale quantum (NISQ) processors. The limitation is due to the circuit depth, rather than the number of qubits. For the first time, we present detailed and completed benchmarks of the five-qubit quantum search algorithm on different quantum processors, including IBMQ, IonQ and Honeywell quantum devices. Besides Grover's algorithm, we also present the implementations of a recently proposed optimized quantum search algorithm [Phys. Rev. A 101, 032346 (2020)]. Noisy simulations are also applied to interpret the results. We report the highest success probability of the five-qubit search algorithm compared to previous works. Our study shows that different quantum processors, with different levels of errors, have different optimal ways to realize the quantum search algorithms. The original Grover's algorithm might not be the best choice. To maximize the power of NISQ computers, designing error-aware algorithms is necessary. (Online) |

12:00 - 13:00 |
Oles Shtanko: Gibbs state samplers with noiseless and noisy random quantum circuits ↓ In the design of quantum algorithms, randomness can play an essential role. In this talk, I will
describe how quantum random circuits can be used to sample quantum states from a Gibbs distribution. I will
describe two novel algorithms in particular. The first is a universal algorithm that can be applied to any local
Hamiltonian. The second algorithm is an efficient way to prepare Gibbs states for Hamiltonians exhibiting
eigenstate thermalization hypothesis. I will provide an overview of the advantages of these algorithms for
noisy quantum hardware and illustrate how optimizing over initially random parameters can mitigate noise.
(joint work with Ramis Movassagh) (Online) |

13:10 - 13:15 | Virtual Group Photo (Online) |

13:15 - 15:05 |
Ramis Movassagh: Panel: Utilizing dissipation and randomness in Quantum Computation/technologies ↓ Panel discussion: Vladimir Korepin, Seth Lloyd, Jarrod McClean.
Moderator: Ramis Movassagh (Online) |

Wednesday, March 16 | |
---|---|

09:00 - 10:00 |
Marius Lemm: Maximal speed for macroscopic particle transport in the Bose-Hubbard model ↓ The celebrated Lieb-Robinson bound asserts the existence of a maximal propagation speed for the
quantum dynamics of lattice spin systems. Analogous general bounds are not available for most
bosonic lattice gases due to their unbounded local interactions. Here we establish a general ballistic
upper bound on macroscopic particle transport in the paradigmatic Bose-Hubbard model. The bound
is the first to cover a broad class of initial states with positive density including Mott states, which
resolves a longstanding problem. It applies to Bose-Hubbard type models on any lattice with not too
long-ranged hopping. The proof rests on controlling the time evolution of a new kind of adiabatic
spacetime localization observable via iterative differential inequalities. Joint work with J. Faupin and
I.M. Sigal. (Online) |

12:00 - 13:00 |
David Pérez-García: Matrix Product Operator Algebras ↓ Matrix Product Operators (MPO) are an ubiquitous mathematical structure in the area of quantum information. Despite their apparent simplicity, they encode very complex problems. In this talk, I will focus on their use to understand exotic (topological) phases of matter. (Online) |

13:10 - 14:10 |
Jarrod McClean: What quantum computer science teaches us about chemistry and quantum advantage in learning from experiments ↓ With the rapid development of quantum technology, one of the leading applications is the simulation
of chemistry. Interestingly, even before full scale quantum computers are available, quantum computer science
has exhibited a remarkable string of results that directly impact what is possible in chemical simulation with any
computer. Some of these results even impact our understanding of chemistry in the real world. In addition,
quantum technology has the potential to revolutionize how we acquire and process experimental data to learn
about the physical world. We show that an experimental setup that transduces data from a physical system to a
stable quantum memory, and processes that data using a quantum computer, could have significant advantages
over conventional experiments in which the physical system is measured and the outcomes are processed using
a classical computer. We prove that, in various tasks, quantum machines can learn from exponentially fewer
experiments than those required in conventional experiments. The exponential advantage holds in predicting
properties of physical systems, performing quantum principal component analysis on noisy states, and learning
approximate models of physical dynamics. 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. (Online) |

14:10 - 15:00 | Informal Discussion (Online) |

Thursday, March 17 | |
---|---|

09:00 - 10:00 |
Ryuhei Mori: Lower bounds on error probability of quantum channel discrimination by the Bures angle and the trace distance ↓ Quantum channel discrimination is a fundamental problem in quantum information science. In this
study, we consider general quantum channel discrimination problems, and derive the lower bounds of
the error probability. Our lower bounds are based on the triangle inequalities of the Bures angle and
the trace distance. As a consequence of the lower bound based on the Bures angle, we prove the
optimality of Grover's search if the number of marked elements is fixed to some integer k. This result
generalizes Zalka's result for k=l. We also present several numerical results in which our lower bounds
based on the trace distance outperform recently obtained lower bounds. (Online) |

12:00 - 13:00 |
Bruno Nachtergaele: Dimerization and the ground state gap for a class of O(n) spin chains ↓ We consider two families of quantum spin chains with $O(n)$-invariant nearest-neighbor interactions
and discuss the ground state phase diagram of this class of models. Using a graphical representation
for the partition function, we provide a proof of a spectral gap above the ground states and
spontaneous breaking of the translation symmetry for an open region in the phase diagram, for all
sufficiently large values of n. (Joint work with Jakob Bjoernberg, Peter Muehlbacher, and Daniel
Ueltschi). (Online) |

13:10 - 14:10 |
Nick Hunter-Jones: Quantum pseudorandomness from domain walls and spectral gaps ↓ Random quantum circuits (RQCs) are valuable constructions in both quantum information and quantum many-body physics. They are a solvable model of strongly-interacting quantum dynamics, efficient implementations of quantum pseudorandomness, and have been the central focus of recent demonstrations of quantum computational advantage. In this talk I’ll discuss some very useful techniques for studying RQCs involving both a statistical-mechanical mapping to lattice model as well as bounding the spectral gap of a local Hamiltonian. Using these approaches, we’ll compute the depth at which RQCs form approximate unitary designs (probability distributions which 'look like' Haar random unitaries) and study how RQCs scramble local noise. (Online) |

14:10 - 15:00 | Informal Discussion (Online) |

Friday, March 18 | |
---|---|

09:00 - 10:00 |
Barbara Jones: Simulation of Open Quantum Systems on Near Term Quantum Computers ↓ Open quantum systems are everywhere in real life, whether it is systems exposed to temperature,
electric field, or anything that causes nonequilibrium decay and/or driving. We find that the study of
open quantum systems has particular promise in the area of physics. We will discuss
practical models we have run on quantum hardware, which turns out to be an excellent platform for
such simulations, being inherently robust against quantum hardware errors even with deep circuits.
We give two examples: 1) we simulate one thousand steps of time evolution for an infinite (U=0)
Hubbard model in a driving electric field while cooled by a temperature bath, and calculate the
current through the system; and 2) we simulate the thermalization of two interacting electrons in an
orbital, a Hubbard atom, in a magnetic field. These problems were solved using circuits containing
up to two thousand entangling gates on quantum computers made available by IBM, showing no
signs of decreasing fidelity at long times. Our results demonstrate that our algorithms for simulating
open quantum systems, analysis and execution of very long runs on current quantum computers and
associated error correction, are able to far outperform similarly complex non-dissipative algorithms
on noisy hardware. Our two examples are the basic building blocks of many condensed matter
physics systems, and we anticipate their demonstrated robustness to hold with increasing
complexity of open quantum problems. Quantum computing is an inherently probabilistic process,
and I will discuss some applications to quantum information as well. (Online) |

12:00 - 13:00 |
Kristan Temme: Probabilistic error cancellation with sparse Pauli-Lindblad models on noisy quantum processors ↓ Error-mitigation techniques can enable access to accurate estimates of physical observables that are otherwise biased by noise in pre-fault-tolerant quantum computers. One particularly general error-mitigation technique is probabilistic error cancellation (PEC), which effectively inverts a well-characterized noise channel to produce noise-free estimates of observables. Experimental realizations of this technique, however, have been impeded by the challenge of learning correlated noise in large quantum circuits. In this work, we present a practical protocol for learning a sparse noise model that scales to large quantum devices and is efficient to learn and invert. These advances enable us to demonstrate PEC on a superconducting quantum processor with crosstalk errors, thereby revealing a path to error-mitigated quantum computation with noise-free observables at larger circuit volumes. (https://arxiv.org/abs/2201.09866) (Online) |

13:00 - 13:15 | Ramis Movassagh: Closing Remarks (Online) |