Sarah Sheldon

Abstract Quantum computations promise the ability to solve problems intractable in the classical setting. Restricting the types of computations considered often allows to establish a provable theoretical advantage by quantum computations, and later demonstrate it experimentally. In this paper, we consider space-restricted computations, where input is a read-only memory and only one (qu)bit can be computed on. We show that n-bit symmetric Boolean functions can be implemented exactly through the use of quantum signal processing as restricted space quantum computations using O(n^2) gates, but some of them may only be evaluated with probability 1/2+O(n/sqrt{2}^n) by analogously defined classical computations. We experimentally demonstrate computations of 3-, 4-, 5-, and 6-bit symmetric Boolean functions by quantum circuits, leveraging custom two-qubit gates, with algorithmic success probability exceeding the best possible classically. This establishes and experimentally verifies a different kind of quantum advantage---one where quantum scrap space is more valuable than analogous classical space---and calls for an in-depth exploration of space-time tradeoffs in quantum circuits.

Abstract Development of quantum hardware has accelerated in recent years and quantum systems with tens of qubits and error rates in the 10-2 range are now reliable and accessible. The trajectory of this development begs the question: how can we make near term systems useful without quantum error correction? The answer is that we need new and diverse advancements in theory, software, and hardware to allow us to approach ever harder problems. This talk will focus in particular on using classical resources to augment the capabilities of today’s quantum hardware, whether through classical post processing techniques or classical computations within a quantum experiment. I will discuss recent work performed on IBM Quantum systems to demonstrate error mitigation, benchmarking techniques for measuring progress, and strategies for extending the range of accessible applications.