NISQ Computing

Motivation

Shor's algorithm - how many qubits does it take to factor an integer ?

Textbook examples of quantum algorithm largely assume that qubits and gates are not subject to noise. In the absence of noise, to factor and integer ,ade of

1024

bits takes about

2050

qubits and over

10^{9}

gates

In the presence of noise, quantum error correction has to be incorporated into the computation, adding a large overhead.

Fault-tolerant quantum computations of arbitrary length are not within reach of today's technology (need qubits in the millions)

Algorithms for small number of qubits (in the

\sim 100

) and limite coherence time will need to offload pre and post-processing to classical computers. Noisy Intermediate Scale quantum (NISQ) computed is thriving field of research:

$50 - 100$ qubits
Limited gate fidelity
Limited qubit connectivity
Limited correction capabilities
$\to$ low depth circuit
Killer apps: simulate correlated matter, machine learning, optimization

Variational Quantum Algorithms

Variational Quantum Algorithms are a hybrird quantum-classical approach.

Goal: finding ground state of a Hamiltonian

H

, or alternatively, optimizing a cost function

Choose a good Ansatz
$| ψ (θ) ⟩$
Design a quantum circuit that implements
$| ψ (θ) ⟩$
Measure cost function
$E_{θ} = ⟨ ψ (θ) | H | ψ (θ) ⟩$
Use classical optimizer to find optimal
$θ^{\*}$

VQA consist of a quantum processor that can prepare quantum states belonging to a parameterized class

{ψ (θ) ⟩}

efficiently and an external loop (running on classical hardware) that optimizes its parameters

The absence of error correcting means that the effective error rate will be non-vanishing, and as a consequence, the length of the possible circuit will be bounded

VQA: Inner routine

The inner routine prepares a state parameterized by

θ

Quantum Approximate Optimization Algorithm

Combinatorial optimization

Combinatorial optimization is about finding an optimal configuration in a set of possible configurations.

In general, combinatorial problems are very big so exhaustive search is not tractable.

There are many methods to tackle optimisation problems, such as Constraint Programming, Branch and Bound/Cut methods, and local search heuristics.

A specific NP-hard problem under consideration, known Quadratic Unconstrained Binary Optimization Problem (QUBO), can be expressed a a local energy problem and therefore phrased as an Ising model. Given a set of spins

s_{i} = \pm 1

, the foal is to find the configuration which minimizes the energy function.

H (s_{1}, \dots s_{N}) = - \sum_{i < j} J_{i j} s_{i} s_{j} - \sum_{i = 1}^{N} h_{i} s_{i}

Simulated Annealing

Heuristic algorithms are used to find approximate solutions to combinatorial problems that, while being suboptimal, are "good enough". Simulated Annealing is a local search heuristic inspired by the physical process of thermal annealing.

SA performs local changes in the current candidate solution and checks whether the new candidate has lower energy. If it does, it becomes the leading candidate, if it does not, one may still accept the new candidate with probability, in the hope that it will help explore the space of solutions. This hill-climbing events become less liekly as the algorithm progresses, and they are controller by an effective temperature parameter.

C'est du recuit simule !

Tunneling effect

Tunneling is the intuition behind QA.

Classicaly, particles with low energy will rebound upon collision with a high energy barrier.

In the quantum setting, it is possible for a low energy particle to pass through the energy wall. This is because quantum particles are not point-like, but rather like wave-packets.