I will present an overview of some ideas presented in the AWS architecture paper ”Building a fault-tolerant quantum computer using concatenated cat codes” by Chamberland et al. This work presented a comprehensive architectural analysis for a fault-tolerant quantum computer based on cat codes concatenated with outer quantum error-correcting codes. This paper covered many aspects of building a quantum computer, and so my presentation will focus on quantum error correction and how one can perform fault-tolerant logic. I will briefly review the idea of cat code qubits and how this leads to biased noise. I will then discuss how the remaining (biased) noise can be tackled using an additional layer of error correction. Then I will discuss how one can perform quantum computations fault-tolerantly, and how biased noise can be exploited in the execution of Toffoli gates.

If you want to do some light reading to learn more, then I can recommend our blog post about this work https://aws.amazon.com/blogs/quantum-computing/designing-a-fault-tolerant-quantum- computer-with-cat-qubits/. And for more details on the cat-qubit aspect of this work, I recommend a talk by Dr Kyungjoo at Byron Bay https://www.youtube.com/watch?v=kWub-XuYcnA

Abstract coming soon!

In the distant future we expect to be using large-scale, nearly perfect quantum computers that aid in drug discovery, break RSA encryption, and outperform supercomputers in certain machine learning tasks. Today we have access to small quantum computers afflicted by noise and error. Somewhere between these two extremes lies a momentous event for the field known as quantum advantage: solving a computational problem of practical value, using a quantum computer in an essential manner. With what tools must we equip ourselves in order to reach quantum advantage as soon as possible? This talk will introduce quantum enhanced sampling, a tool for speeding up a critical component of many near-term quantum algorithms: estimation of quantities encoded in quantum operations. This helps to bridge the gap between several near-term quantum algorithms and their far-term counterparts. We will motivate the need for this tool through recent examples in quantum machine learning and quantum chemistry. Then we will give a pedagogical introduction to quantum enhanced sampling methods. Finally, we will show results demonstrating the performance of this method and will discuss the implications for near-term quantum computing.

As quantum technology rapidly advances, a premier application of interest is the simulation of physical, chemical, and material systems to improve the pathway towards novel design. However, even before large, fault-tolerant devices are available, the study of quantum computer science can shape our perspective on the natural world. In this talk, we will first review some of the techniques that make quantum computers especially promising for the simulation of chemical and material systems. From there, we explore what we have learned about the limits of even quantum computing methods, and their relationship with collecting data from nature. In particular, we’ll cover recent results on the ways in which data can elevate classical learning models beyond conventional classical computation when samples from a quantum computer are provided. We’ll use this to shape an outlook for the future relationship between quantum computing, chemistry, and materials science.

Interference is an essential part of quantum mechanics. However, an important class of Hamiltonians considered are those with ”no sign problem”, where all off-diagonal matrix elements of the Hamiltonian are non-negative. This means that the ground state wave function can be chosen to have all amplitudes real and positive. In a sense, no destructive interference is possible for these Hamiltonians so that they are ”almost classical”, and there are several simulation algorithms which work well in practice on classical computers today. In this talk, I’ll discuss what happens when one considers adiabatic evolution of such Hamiltonians, and show that they still have some power that cannot be efficiently simulated on a classical computer; to be precise and formal, I’ll show this ”relative to an oracle”, which I will explain. I’ll discuss implications for simulation of these problems and open questions.

An ultimate goal of quantum computing is to perform calculations beyond the reach of any classical computer. It is therefore imperative that useful quantum computers be very difficult to simulate classically; otherwise classical computers could be used for the applications envisioned for the quantum ones. Perfect quantum computers are unarguably exponentially difficult to simulate: the classical resources required grow exponentially with the number of qubits N or the depth D of the circuit. This difficulty has triggered recent experiments on deep, random circuits that aim to demonstrate that quantum devices may already perform tasks beyond the reach of classical computing. These real quantum computing devices, however, suffer from many sources of decoherence and imprecision which limit the degree of entanglement that can actually be reached to a fraction of its theoretical maximum. They are characterized by an exponentially decaying fidelity F ∼ (1 − ε)N D with an error rate ε per operation as small as ≈ 1% for current devices with several dozen qubits or even smaller for smaller devices.

In this work, we provide new insights on the computing capabilities of real quantum computers by demonstrating that they can be simulated at a tiny fraction of the cost that would be needed for a perfect quantum computer. Our algorithms compress the representations of quantum wavefunctions using matrix product states (MPS), which are able to capture states with low to moderate entanglement very accurately. This compression introduces a finite error rate ε so that the algorithms closely mimic the behavior of real quantum computing devices. The computing time of our algorithm increases only linearly with N and D in sharp contrast with exact simulation algorithms. We illustrate our algorithms with simulations of random circuits for qubits connected in both one and two dimensional lattices. We find that ε can be decreased at a polynomial cost in computing power down to a minimum error ε∞. Getting below ε∞ requires computing resources that increase exponentially with ε∞/ε. For a two dimensional array of N = 54 qubits and a circuit with Control-Z gates, error rates better than state-of-the-art devices can be obtained on a laptop in a few hours. For more complex gates such as a swap gate followed by a controlled rotation, the error rate increases by a factor three for similar computing time. Our results suggest that, despite the high fidelity reached by quantum devices, only a tiny fraction (∼ 10−8) of the system Hilbert space is actually being exploited.

Reference: Yiqing Zhou, E. Miles Stoudenmire, and Xavier Waintal, “What limits the simulation of quantum computers?” Phys. Rev. X10, 041038 (2020)

Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling, that is beyond the practical reach of modern supercomputers. We examine the constraints on the region of quantum advantage for quantum circuits with a larger number of qubits and gates than experimentally implemented so far. These constraints arise from an analysis that carefully accounts for the number of samples required to ensure a sufficiently small variance of the measured circuit fidelity, a criterion we identify as central to the quantum supremacy claim. At gate fidelities expected in the near-term, we demonstrate that the quantum supremacy region is limited to quantum circuits with a qubit count and circuit depth of a few hundred. Beyond these boundaries, exponentially decaying gate fidelities cause cross-entropy benchmarking to require prohibitively many samples on a quantum computer, either causing a return of a classical advantage or computationally infeasible runtimes, depending on the noise parameters. However, the regime of a quantum runtime advantage grows exponentially with respect to reduced error rates, highlighting the importance of continued progress along this line. Extrapolations of measured error rates suggest that the limiting circuit size for which a computationally feasible quantum runtime advantage in cross-entropy benchmarking can be achieved approximately coincides with expectations for early implementations of the surface code and other quantum error correction methods. Thus, the boundaries of quantum supremacy via random circuit sampling may fortuitously coincide with the advent of scalable, error-corrected quantum computing in the near term.

Ref.: https://arxiv.org/abs/2005.02464

The advent of widely available computing power has spawned a whole research field that we now call computational physics. Today, we may be on the cusp of a similar paradigm shift as programmable qubit devices enable one to run experiments on a platform of actual physical quantum states. Here we use the commercially available D-Wave DW-2000Q device to build and probe a state of matter that has not been observed or fabricated before. The topological phase that we build has been widely sought for many years and is a candidate platform for quantum computation. While we cannot observe the full quantum regime due to the limitations of the current device, we do observe unmistakable signatures of the phase in its classical limit at the endpoint of the quantum annealing protocol. In the process of doing so, we identify additional features that a programmable device of this sort would need in order to implement fully functional topological qubits. It is a testament to technological progress that a handful of theorists can observe and experiment with new physics while being equipped only with remote access to a commercial device.

Quantum cryptography is known for enabling functionalities that are unattainable using classical information alone. Recently, Secure Software Leasing (SSL) has emerged as one of these areas of interest. Given a target circuit C from a circuit class, SSL produces an encoding of C that enables a recipient to evaluate C, and also enables the originator of the software to verify that the software has been returned – meaning that the recipient has relinquished the possibility of any further use of the software. Clearly, such a functionality is unachievable using classical information alone, since it is impossible to prevent a user from keeping a copy of the software. Recent results have shown the achievability of SSL using quantum information for a class of functions called compute-and-compare (these are a generalization of the well-known point functions). These prior works, however all make use of setup or computational assumptions. Here, we show that SSL is achievable for compute-and-compare circuits without any assumptions. Our technique involves the study of quantum copy-protection, which is a notion related to SSL, but where the encoding procedure inherently prevents a would-be quantum software pirate from splitting a single copy of an encoding for C into two parts, each of which enables a user to evaluate C. We show that point functions can be copy-protected without any assumptions, for a novel security definition involving one honest and one malicious evaluator; this is achieved by showing that from any quantum message authentication code, we can derive such an honest-malicious copy-protection scheme. We then show that a generic honest-malicious copy-protection scheme implies SSL; by prior work, this yields SSL for compute-and-compare functions.

Based on joint work with Stacey Jeffery, S ́ebastien Lord, Supartha Podder and Aarthi Sundaram. arXiv:2101.12739

The "quantum Cook-Levin Theorem" rigorously justified, assuming standard complexity theoretic conjectures, the long-standing physics intuition that studying quantum many-body systems is "hard": Indeed, the theorem says that estimating the ground state energy of such a system is QMA-complete, for QMA the quantum analogue of NP. However, a more natural physical problem had escaped the community's attention until recent years: How hard is it to simulate local measurements on ground states of many-body systems (denoted APX-SIM)? Indeed, this is arguably among the most fundamental questions facing experimentalists aiming to understand the low-temperature properties of physical systems. In this talk, we discuss a sequence of works which show that this problem is, perhaps surprisingly, even harder than QMA - it is P^QMA[log]-complete, for P^QMA[log] the class of decision problems solvable in polynomial time with access to logarithmically many queries to a QMA oracle. Along the way, we will see that this odd-looking class captures not only other physical problems such as estimating spectral gaps of local Hamiltonians, but that the APX-SIM problem remains hard even on ever-simpler-looking systems, such as the 2D Heisenberg interaction and 1D translationally invariant systems.

This talk covers a sequence of works, starting with one of Andris Ambainis, followed by joint works with (in alphabetical order) Johannes Bausch (U Cambridge), Stephen Piddock (U Bristol), Justin Yirka (UT Austin), and James Watson (U College London).

Exactly solvable models are essential in physics. For many-body spin-1/2 systems, an important class of such models consists of those that can be mapped to free fermions hopping on a graph. We provide a complete characterization of models which can be solved this way. Specifically, we reduce the problem of recognizing such spin models to the graph-theoretic problem of recognizing line graphs, which has been solved optimally. A corollary of our result is a complete set of constant-sized commutation structures that constitute the obstructions to a free-fermion solution. We find that symmetries are tightly constrained in these models. Pauli symmetries correspond to either: (i) cycles on the fermion hopping graph, (ii) the fermion parity operator, or (iii) logically encoded qubits. Clifford symmetries within one of these symmetry sectors, with three exceptions, must be symmetries of the free-fermion model itself. We demonstrate how several exact free-fermion solutions from the literature fit into our formalism and give an explicit example of a new model previously unknown to be solvable by free fermions.

Based on arXiv:2003.05465.

Quantum devices promise efficient simulation of quantum many-body systems. Of particular interest are properties at low temperature where, to a good approximation, the system is in its ground state. Thus, a quantum simulation requires a quantum circuit that maps a fiducial state to the ground state of interest. This problem is generally QMA-complete, so the existence of a general-purpose efficient procedure is believed to be impossible. Nonetheless, heuristic methods could be sufficiently fast for intermediate-size problems.

We present an estimate of the resources required to prepare the ground state of a quantum many-body system on a quantum computer. This estimate is made possible using a combination of tensor network methods and analytic upper bounds. Our procedure can also be used to optimize certain design parameters for specific instances. Lastly, we propose and benchmark an improved quantum state preparation algorithm. We find that it reduces the circuit T-depth by a factor as large as 10⁷ for intermediate-size lattices, an impressive gain for fault-tolerant quantum computers.

Based on arXiv:2006.04650.

With the increasing size of quantum processors, the sub-modules that constitute the processor will become too large to accurately simulate on a classical computer. Therefore, one would soon have to fabricate and test each new design primitive and parameter choice in time-consuming coordination between design, fabrication, and experimental validation. To circumvent this slow-down, we address the question of how one can design and test the performance of the sub-modules of next-generation quantum devices--by using existing quantum computers [1, 2]. Focusing on superconducting transmon processors as a prominent hardware platform, we compute the static and dynamic properties of individual and coupled transmons. We show how the energy spectra of transmons can be obtained by variational hybrid quantum-classical algorithms that are well-suited for near-term noisy quantum computers. We also numerically demonstrate how single-and two-qubit gates can be realized via Suzuki-Trotter decomposition for digital quantum simulation. Our methods pave a new way towards designing candidate quantum processors when the demands of calculating sub-module properties exceed the capabilities of classical computing resources. The encoding scheme used throughout this work is the Gray encoding [3] and the popular science article related to the works can be found at https://aspuru.substack.com/p/designing-quantum-hardware-with-quantum

References:

[1] Thi Ha Kyaw, Tim Menke, Sukin Sim, Nicolas PD Sawaya, William D Oliver, Gian Giacomo Guerreschi, Alán Aspuru-Guzik, arXiv2006.03070 (2020).

[2] Jakob Kottmann, Mario Krenn, Thi Ha Kyaw, Sumner Alperin-Lea, Alán Aspuru-Guzik, arXiv:2006.03075 (2020).

[3] Nicolas PD Sawaya, Tim Menke, Thi Ha Kyaw, Sonika Johri, Alán Aspuru-Guzik, Gian Giacomo Guerreschi, npj Quantum Information 6, 1-13 (2020).