Lecture

Quantum Approximate Optimization Algorithm

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 introduces the Quantum Approximate Optimization Algorithm (QAOA) as a method to solve combinatorial optimization problems using quantum computers. The instructor explains the principles behind QAOA and its application to Boolean Satisfiability (SAT) problems. The lecture covers the formulation of optimization problems in a quantum setting, focusing on the Ising Spin-glass problem and K-SAT problems. Various examples and algorithms are discussed to illustrate the effectiveness of QAOA in solving complex optimization problems.

Official source

Related concepts (23)

Boolean satisfiability problem

In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable.

2-satisfiability

In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable.

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.

Superconducting quantum computing

Superconducting quantum computing is a branch of solid state quantum computing that implements superconducting electronic circuits using superconducting qubits as artificial atoms, or quantum dots. For superconducting qubits, the two logic states are the ground state and the excited state, denoted respectively. Research in superconducting quantum computing is conducted by companies such as Google, IBM, IMEC, BBN Technologies, Rigetti, and Intel. Many recently developed QPUs (quantum processing units, or quantum chips) utilize superconducting architecture.

P versus NP problem

The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved. The informal term quickly, used above, means the existence of an algorithm solving the task that runs in polynomial time, such that the time to complete the task varies as a polynomial function on the size of the input to the algorithm (as opposed to, say, exponential time).

Related lectures (64)

Quantum Approximate Optimization Algorithm

Explores the Quantum Approximate Optimization Algorithm and its application in solving optimization problems efficiently using quantum adiabatic evolution.

Quantum Adiabatic Optimization: Combinatorial Problems

Explores Quantum Approximate Optimization Algorithm for solving combinatorial problems efficiently.

NISQ Algorithms and the VQE

Explores NISQ algorithms, with a focus on the VQE method and error mitigation techniques.

Quantum Computational Advantage: Recent Progress and Next Steps

Explores recent progress in quantum computational advantage and discusses the challenges in achieving quantum supremacy.

Solving Parity Games in Practice