Lecture

Quantum Computational Advantage: Recent Progress and Next Steps

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture by the instructor covers the concept of quantum computational advantage, also known as quantum supremacy, discussing its importance and the challenges in achieving it. The lecture explores recent progress in quantum advantage protocols and introduces the instructor's approaches, including quantum machine learning for language translation and solving combinatorial optimization problems. The presentation delves into the complexity-theoretic foundation of quantum advantage, the linear cross-entropy benchmark, and spoofing algorithms. It also touches upon quantum advantage in neural sequence modeling and the potential for proving exponential speedup in quantum computing. The lecture concludes with a discussion on efficient verifiable quantum advantages and classical combinatorial optimization problems encoded using Rydberg atom arrays.

Official source

Ontological neighbourhood

Theoretical computer science

Theory of computation: Quantum computing

Related concepts (32)

Quantum computing

A quantum computer is a computer that exploits quantum mechanical phenomena. At small scales, physical matter exhibits properties of both particles and waves, and quantum computing leverages this behavior, specifically quantum superposition and entanglement, using specialized hardware that supports the preparation and manipulation of quantum states. Classical physics cannot explain the operation of these quantum devices, and a scalable quantum computer could perform some calculations exponentially faster than any modern "classical" computer.

Quantum supremacy

In quantum computing, quantum supremacy, quantum primacy or quantum advantage is the goal of demonstrating that a programmable quantum computer can solve a problem that no classical computer can solve in any feasible amount of time, irrespective of the usefulness of the problem. The term was coined by John Preskill in 2012, but the concept dates back to Yuri Manin's 1980 and Richard Feynman's 1981 proposals of quantum computing.

Quantum annealing

Quantum annealing (QA) is an optimization process for finding the global minimum of a given objective function over a given set of candidate solutions (candidate states), by a process using quantum fluctuations. Quantum annealing is used mainly for problems where the search space is discrete (combinatorial optimization problems) with many local minima; such as finding the ground state of a spin glass or the traveling salesman problem. The term "quantum annealing" was first proposed in 1988 by B. Apolloni, N.

Linear optical quantum computing

Linear optical quantum computing or linear optics quantum computation (LOQC) is a paradigm of quantum computation, allowing (under certain conditions, described below) universal quantum computation. LOQC uses photons as information carriers, mainly uses linear optical elements, or optical instruments (including reciprocal mirrors and waveplates) to process quantum information, and uses photon detectors and quantum memories to detect and store quantum information.

Quantum cryptography

Quantum cryptography is the science of exploiting quantum mechanical properties to perform cryptographic tasks. The best known example of quantum cryptography is quantum key distribution which offers an information-theoretically secure solution to the key exchange problem. The advantage of quantum cryptography lies in the fact that it allows the completion of various cryptographic tasks that are proven or conjectured to be impossible using only classical (i.e. non-quantum) communication.

Related lectures (64)

Quantum Computation: Mechanisms and Advantages of Restricted Models

Covers the mechanisms behind quantum computation and explores the advantages of restricted computational models.

The Deutsch and Deutsch-Jozsa Algorithms

Covers the Deutsch and Deutsch-Jozsa algorithms in quantum computing, explaining the principles behind them and their implications.

Quantum Computing: Introduction

Covers quantum computing basics, quantum algorithms, error correction, and quantum bit manipulation.

Quantum Computing Basics

Covers the basics of quantum computing, focusing on superconducting qubits, scaling challenges, and potential applications.

Quantum and Nanocomputing