Algorithms

\[% https://latex.wikia.org/wiki/List_of_LaTeX_symbols % https://www.overleaf.com/learn/latex/Main_Page % % latex commands for quantum mechanics: bra & kets \newcommand{\bra}[1]{\left<#1\right|} \newcommand{\ket}[1]{\left|#1\right>} \newcommand{\bk}[2]{\left<#1\middle|#2\right>} \newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>} % % general shortcuts \newcommand{\bm}[1]{\boldsymbol{#1}} % bold math \newcommand{\super}[2]{#1 {}^{#2}} % superscript \newcommand{\half}{\frac{1}{2}} % % hats together with subscripts or superscript (e.g. for angular momentum) \newcommand{\hatb}[1]{\bm{\hat{#1}}} % hat + bold \newcommand{\hatsub}[2]{\hat{{#1}_{#2}}} % hat + subscript \newcommand{\hatsup}[2]{\super{\hat{#1}}{#2}} % hat + superscript \newcommand{\hatsubsup}[3]{\super{\hat{#1}}{#3}_{#2}} % hat + sub + superscript % % Pauli operators \newcommand{\pauliX}{\hatsubsup{\sigma}{X}{}} \newcommand{\pauliY}{\hatsubsup{\sigma}{Y}{}} \newcommand{\pauliZ}{\hatsubsup{\sigma}{Z}{}} \newcommand{\pauliP}{\hatsubsup{\sigma}{+}{}} \newcommand{\pauliM}{\hatsubsup{\sigma}{-}{}} \newcommand{\pauliPM}{\hatsubsup{\sigma}{\pm}{}} % % derivates \newcommand{\odv}[2]{\frac{\textrm{d} #1}{\textrm{d} #2}} \newcommand{\pdv}[2]{\frac{\partial #1}{\partial #2}}\]

Complexity classes

  • Refresher: P, NP, PSPACE, [B3] section 3.2.4,

  • Quantum computational complexity [B3] section 4.5.5

Overview

  • Quantum algorithms: an overview [94]

  • an extensive list in Quantum Algorithm Zoo [M19]

  • a review about Variational Quantum Algorithms [R7]

  • Define oracles…

  • see also about the expressiveness of parametrized quantum circuit (PQC) ansatzes [M4]

  • Examples described in this section

    • “Pure” quantum algorithms: Shor | Grover | HHL

    • Hybrid quantum-classical variational algorithms: QAOA | VQE

Pure Quantum Algorithms

“Pure” quantum in contrast to hybrid quantum-classical algorithms, they require error-correction.

Shor

The Shor algorithm describes a way to break the RSA public-key cryptosystem in polynomial time. It uses Quantum Fourier transform and Phase estimation, which both are general building blocks for quantum algorithms.

Grover

  • Grover, the quantum search algorithm, incl. Amplitude amplification
    “Having a phone book (sorted by name), find the name corresponding to a given phone number”.
    classical: \(O(N)\)
    quantum: \(O(\sqrt{N})\)
  • Grover algorithm is optimal [16]:
    “relative to an oracle chosen uniformly at random, with probability 1, the class NP cannot be solved on a quantum Turing machine in time \(o(2^{n/2})\)”
    “recent work of Grover shows how to accept the class NP relative to any oracle on a quantum computer in time \(O(2^{n/2})\).”

  • An approaching to TSP and SAT using Grover’s quantum search algorithm:

    • How the quantum search algorithm works [M25], about the traveling salesperson problem (TSP):
      “consider a variation on TSP, namely, searching for a route shorter than some specified threshold distance, \(T\).”
    • Solving Satisfiability Problems using Grover’s Algorithm [M39]
      “While it doesn’t make sense to use Grover’s algorithm on 3-sat problems, the techniques here can be applied to the more general case (k-SAT, discussed in the next section) for which Grover’s algorithm can outperform the best classical algorithm.”

HHL

Solving Linear Systems of Equations [54]

“We consider the case where one doesn’t need to know the solution x itself, but rather an approximation of the expectation value of some operator associated with x.”

Variational Quantum Algorithms

Hybrid quantum-classical algorithms, they are designed to work also on NISQ hardware and tolerate some amount of noise. The classical part is an optimization task.

VQE

Quantum Advantage

For estimations of the required hardware and claims of quantum advantage, see Quantum Advantage in the State of the Art section.

References: Cirac [L2] lecture 15 ; Qiskit tutorials [M39].