Variational Quantum Algorithms

How do they work?

Michał Stęchły

13th July 2020�Warsaw QC group

Presentation plan

1. About
2. Intro to VQA
3. VQE
4. QAOA
5. NISQ
6. VQA anatomy

About me

• Quantum Software Engineer at Zapata Computing
• Building Orquestra
• Implementing algorithms
• Helping with research projects
• Quantum Open Source Foundation
• QC Mentorship program
• Q4Climate
• Getting it all started!
• Musty Thoughts (blog)�

​

What is VQA?

Source: http://openqemist.1qbit.com/docs/vqe_microsoft_qsharp.html

Examples of VQA

• VQE
• QAOA
• QNNs

Variational Quantum Eigensolver

Variational principle

Important concepts

• Hamiltonian
• Eigenstate
• State energy
• Ground state
• Ground state energy

By definition:

• Energy of any state is greater or equal ground state energy

Why do we care about ground state energy?

• It’s useful
• It’s hard to get with classical computing

What do we need?

• Some method of encoding the problem
• Some method for preparing the parametrizable state
• Some method for finding a good set of parameters

Pauli Matrices

​

​

​

​

​

​

Good source: http://www.warrenalphonso.com/qc/hubbard

Simple example - hydrogen

H =

-0.1673 * I + 0.1625 * Z0 + 0.1625 * Z1 + -0.1974 * Z2 + -0.1974 * Z3

+ 0.1658 * Z0 Z1 + 0.1172 * Z0 Z2 + 0.1633 * Z0 Z3 + 0.1633 * Z1 Z2 + 0.1172 * Z1 Z3 + 0.1716 * Z2 Z3

+ -0.0461 * X0 X1 Y2 Y3 + 0.0461 * X0 Y1 Y2 X3 + 0.0461 * Y0 X1 X2 Y3 + -0.0461 * Y0 Y1 X2 X3

​

​

​

Good source: http://www.warrenalphonso.com/qc/hubbard

Ansatz!

Source: https://arxiv.org/abs/1905.10876

What a good ansatz has?

• High (enough) expressibility
• Low number of parameters
• Low depth
• “Hardware-awareness”

How to obtain energy?

• Measure and calculate the expectation value

Simple example - hydrogen

H =

-0.1673 * I + 0.1625 * Z0 + 0.1625 * Z1 + -0.1974 * Z2 + -0.1974 * Z3

+ 0.1658 * Z0 Z1 + 0.1172 * Z0 Z2 + 0.1633 * Z0 Z3 + 0.1633 * Z1 Z2 + 0.1172 * Z1 Z3 + 0.1716 * Z2 Z3

+ -0.0461 * X0 X1 Y2 Y3 + 0.0461 * X0 Y1 Y2 X3 + 0.0461 * Y0 X1 X2 Y3 + -0.0461 * Y0 Y1 X2 X3

​

​

​

Good source: http://www.warrenalphonso.com/qc/hubbard

How to measure?

RY(pi/2)

Classical optimization

What a QPU does:

• Given a set of parameters, returns us a set of measurements.

What a classical computer does:

• Given a set of measurements calculates the energy value (it’s usually some kind of averaging)
• Performs optimization procedure
• Calculates what a new set of parameters should be
• Checks whether we have reached the minimum
• Makes sure we don’t make more iterations than we should have done

​

• ​

Example

H = 2Z + X + I

H = H₁ + H₂ + H₃

E = E₁ + E₂ + E₃

|𝚿> = RY(𝚹)

Example

H = 2Z + X + I

E (𝚹 = 0) = 2 + 0 + 1

E (𝚹 = π) = -2 + 0 + 1

Example

Quantum Approximate Optimization Algorithm

Why do we care about combinatorial optimization?

It’s everywhere!

MaxCut

MaxCut

QAOA-related concepts

• Adiabatic Quantum Computing
• Ising Models
• Time evolution
• Trotterization

Adiabatic Quantum Computing

Adiabatic Quantum Computing - issues

​

• Isolation
• Time
• Universal gate-based quantum computer

Ising Models

Source: Thermalisation and Relaxation of Quantum Systems, Sascha Wald

Ising Models

Source: Thermalisation and Relaxation of Quantum Systems, Sascha Wald

Ising Model – MaxCut

​

Source: https://lucaman99.github.io/new_blog/2020/mar16.html

Time evolution

Function approximation

Trotterization

Source: https://ocw.mit.edu/courses/nuclear-engineering/22-51-quantum-theory-of-radiation-interactions-fall-2012/lecture-notes/MIT22_51F12_Ch5.pdf

What’s QAOA?

Source: https://arxiv.org/abs/1411.4028

QAOA – relation to AQC

Source: https://arxiv.org/abs/1712.05304

QAOA – cost Hamiltonian

Source: https://arxiv.org/abs/1411.4028

QAOA - mixer Hamiltonian

​

Source: https://arxiv.org/abs/1411.4028

QAOA - mixer Hamiltonian

​

What makes a good mixer Hamiltonian?

• Easy to implement
• Does not commute with cost Hamiltonian

Example

​

Example

​

Relationship between VQE and QAOA

QAOA can be viewed as a special case of VQE.

However:

• The ansatz form is limited
• Restricted to Ising Hamiltonian
• Different goal of the algorithm

​

NISQ

NISQ challenges

• Noise
• Life time of qubits
• Number of qubits
• Set of available gates
• Connectivity

​

How does it affects us?

​

Source: https://arxiv.org/abs/2004.04197

Why VQA are good for NISQ?

• Usually allow for variable circuit depth
• They show some resistance to noise
• They don’t necessarily require a lot of qubits

​

Structure of VQA

What about...

• Chip layout?
• Gate set?

​

What about...

• Ansatz?
• Readout correction?
• Measurement strategy?
• Grouping strategy?
• Shots allocation?
• Noise models (for simulation)?

​

​

Executable circuit

QVM/QPU

Measurements

Abstract circuit

Compiler

QPU specs

Ansatz

Parameters

Noise models

Readout correction

Measurement strategy

Target operator

Grouping strategy

“Shots budget”

What about...

• Problem definition?
• Constraints?
• Cost function?
• Parameter bounds?
• Optimizer?
• Algorithm?
• Algorithm params?
• Initial parameters?
• Gradient calculation?

​

​

VQA

PROBLEM DEFINITION

Cost Function

Parameters

Target operator

Ansatz

Constraints

Parameter bounds

Gradient calculation strategy

Parameter initialization strategy

Initial optimizer settings

Measurement strategy

Optimizer

Challenges of VQAs

• Ansatz design
• Optimization
• Barren plateaus
• Just optimization
• Calculating gradients
• Measurement problem
• Provable speedups?
• All the various possible improvements
• How to benchmark?
• Simulation vs Experiment

Summary

What have we covered?

• VQE
• QAOA
• Algorithms for NISQ era
• Structure of VQAs

Thank you!

www.mustythoughts.com

Twitter: @mstechly