COMP90084 Quantum Software Fundamentals

1. Matrix Cookbook
2. Quantum Computing for Computer Scientists

Prerequisites 1. Complex Numbers

• $i^2 = -1, i^3 = -i, i^4 = 1$
• can also be represented as $(a, b)$, where $a$ is the real part and $b$ is the imaginary part
• commutative 可交换的: $c_1 + c_2 = c_2 + c_1, c_1c_2 = c_2c_1$
• associative 结合的: $(c_1 + c_2) + c_3 = c_1 + (c_2 + c_3), (c_1c_2)c_3 = c_1(c_2c_3)$
• distributive 分配的: $c_1(c_2 + c_3) = c_1c_2 + c_1c_3$
• addition:
  • let $c_1 = (a_1, b_1), c_2 = (a_2, b_2)$
  • then $c_1 + c_2 = (a_1 + a_2, b_1 + b_2)$
• multiplication:
  • let $c_1 = (a_1, b_1), c_2 = (a_2, b_2)$
  • then $c_1c_2 = (a_1a_2 - b_1b_2, a_1b_2 + a_2b_1)$
• subtraction: $c_1 - c_2 = c_1 + (-c_2)$
• division:
  • let $(x,y) = \frac{(a_1, b_1)}{(a_2, b_2)}$
    • then $(a_1, b_1) = (a_2, b_2)(x, y)$
  • $a_1 = a_2x - b_2y, b_1 = a_2y + b_2x$
    • $a_1a_2 + b_1b_2 = (a_2^2 + b_2^2)x$
    • $a_2b_1 - a_1b_2 = (a_2^2 + b_2^2)y$
  • then
    • $x = \frac{a_1a_2 + b_1b_2}{a_2^2 + b_2^2}$
    • $y = \frac{a_2b_1 - a_1b_2}{a_2^2 + b_2^2}$
• modulus: $|c| = \sqrt{a^2 + b^2}$
• algebraically complete: any polynomial equation has a solution in such a field 所有的代数方程的解都在这个域中
  • $R$ 实数不是
  • $C$ 复数是
• conjugate:
  • if $c = (a, b)$
  • $\bar{c} = (a, -b)$
• field isopmorphism: a bijective homomorphism between two fields
  • bijection: one-to-one and onto 单射和满射
  • 每一个输入值都有正好一个输出值以及每一个输出值都有正好一个输入值
• parallelogram law 平行四边形定律
  • 向量相加
• polar/Catesian representation
  • 极坐标系
  • $(\rho, \theta)$

Prequisites 2. Vector Spaces

• addition: $(V+W)[j] = V[j] + W[j]$

  • let $V = \begin{bmatrix} v_1 \\ v_2 \end{bmatrix}, W = \begin{bmatrix} w_1 \\ w_2 \end{bmatrix}$
  • then $V + W = \begin{bmatrix} v_1 + w_1 \\ v_2 + w_2 \end{bmatrix}$
  • commutative: $V + W = W + V$
  • associative: $(V + W) + X = V + (W + X)$

• inverse: $V + (-V) = 0$

• Abelian group 阿贝尔群: addition, inverse, associative, commutative

• scalar: an abitrarily complex number

• multiply an element by a scalar: $(c \cdot V)[j] = c \times V[j]$

• transpose 转置: $V^T[j, k] = V[k, j]$

• conjugate 共轭，复数相反，实数不变: $\overline{V}[j] = \overline{V[j]}$

• adjoint/dagger 伴随，转置+共轭: $V^\dagger[j, k] = \overline{V[k, j]}$

  • $(V^\dagger)^\dagger = V$
  • $(c \cdot V)^\dagger = \overline{c} \cdot V^\dagger$

• matrix multiplication: $\star$

  • $(A \star B)^T = B^T \star A^T$
  • $\overline{A \star B} = \overline{A} \star \overline{B}$
  • $(A \star B)^\dagger = B^\dagger \star A^\dagger$

• isomorphism 同构，双射（双向一一对应）

  • 可以认为两个空间性质相同，仅命名不同

• linear independence 线性无关

  • linear combination: $V = c_1v_1 + c_2v_2 + \cdots + c_nv_n$
  • 一组向量的线性组合不等于0
  • $0=c_1v_1 + c_2v_2 + \cdots + c_nv_n$ only when $c_1 = c_2 = \cdots = c_n = 0$
  • basis: a set of linearly independent vectors that span the space ${v_1, v_2, \cdots, v_n}$
  • canonical/standard basis: a set of vectors with one 1 and the rest are 0
  • dimension: the number of vectors in the basis

• trace: sum of the diagonal elements

  • $Tr(A) = \sum_{i=1}^{n} A[i, i]$

• eigenvalue and eigenvector 特征值和特征向量

  • for a matrix $A$, if $Av = \lambda v$, then $\lambda$ is the eigenvalue and $v$ is the eigenvector

• symmetric matrix 对称矩阵

  • $A = A^T$

• hermitian matrix 共轭转置矩阵

  • $A = A^\dagger$

• invertible matrix 可逆矩阵

  • $A^{-1} \star A = A \star A^{-1} = I$

• unitary matrix 幺正矩阵

  • $A^\dagger \star A = A \star A^\dagger = I$

• tensor product 张量积

  • $A \otimes B = \begin{bmatrix} a_{11}B & a_{12}B \\ a_{21}B & a_{22}B \end{bmatrix}$

• orthogonal:

  • for two vectors $v_1 = (a_1, b_1), v_2 = (a_2, b_2)$
  • if $v_1 \cdot v_2 = 0$, then $v_1$ and $v_2$ are orthogonal
  • $v_1 \cdot v_2 = a_1a_2 + b_1b_2$

• normalised:

  • $v \cdot v = 1$
  • $v = \frac{v}{|v|} = \frac{v}{\sqrt{v \cdot v}}$

Bra-ket Notation

• also called Dirac notation

• linear algebra in complex vector space

• ket 表示量子态向量，通常用于描述系统的状态: $|v\rangle$

• bra 表示量子态向量的共轭转置（Hermitian 共轭），用于内积计算: $\langle v|$

• $|0 \rangle = \begin{array}{cc} \begin{array}{c} 0 \\ 1 \end{array} \begin{bmatrix} 1 \\ 0 \end{bmatrix} \end{array}$

• $|1\rangle = \begin{array}{cc} \begin{array}{c} 0 \\ 1 \end{array} \begin{bmatrix} 0 \\ 1 \end{bmatrix} \end{array}$

• $|+\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}}$

• $|-\rangle = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$

• $|i\rangle = \frac{|0\rangle + i|1\rangle}{\sqrt{2}}$

• $|-i\rangle = \frac{|0\rangle - i|1\rangle}{\sqrt{2}}$

• inner product: $\langle 0 | 1 \rangle = 0$

  • "bracket"
  • also called dot product/scalar product
  • result in a scalar
  • $\langle 0 | 1 \rangle = \begin{bmatrix} 1 & 0 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 1*0 \\ 0*1 \end{bmatrix} = 0$

• outer product: $| 0 \rangle\langle 1 |$

  • result in a matrix
  • $| 0 \rangle\langle 1 | = \begin{bmatrix} 1 \\ 0 \end{bmatrix} \begin{bmatrix} 0 & 1 \end{bmatrix} = \begin{bmatrix} 1*0 & 1*1 \\ 0*0 & 0*1 \end{bmatrix} = \begin{bmatrix} 0 & 1 \\ 0 & 0 \end{bmatrix}$

• $|0 \rangle\langle 0 | = \begin{bmatrix} 1 \\ 0 \end{bmatrix} \begin{bmatrix} 1 & 0 \end{bmatrix} = \begin{bmatrix} 1*1 & 1*0 \\ 0*1 & 0*0 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}$

• $|1 \rangle\langle 1 | = \begin{bmatrix} 0 \\ 1 \end{bmatrix} \begin{bmatrix} 0 & 1 \end{bmatrix} = \begin{bmatrix} 0*0 & 0*1 \\ 1*0 & 1*1 \end{bmatrix} = \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix}$

• $e^{i\theta} = \cos(\theta) + i\sin(\theta)$

  • 量子比特的旋转可以表示为一个向量在复平面上的旋转
  • 旋转操作可以用幺正矩阵（如 Pauli 矩阵和旋转矩阵）来表示
  • 这些矩阵可以通过指数映射（如 e 的幺正矩阵次方）来生成

Kets Algebra

• $|\Psi\rangle + |\Psi'\rangle = (c_0 + c_0')|0\rangle + (c_1 + c_1')|1\rangle + \cdots + (c_n + c_n')|n\rangle$
• $c|\Psi\rangle = cc_0|0\rangle + cc_1|1\rangle + \cdots + cc_n|n\rangle$

1. Linear Algebra to Quantum Computing

• 为什么学？
  • 解决经典计算机无法解决的问题
  • 对于量子纠错可能性的乐观主义
• 这是什么？
  • 基于量子力学的计算机学说
  • 量子化学，量子深度学习
  • 后量子密码学
• Physical Qubits:
  • Particles with polarization(photon) 光子
  • Trapped ions 离子阱
  • Cold Atoms 冷原子
  • Quantum dots 量子点
  • Using Defect in Crystals 晶体缺陷
  • Superconductors 超导体
• Major Players
  • IBM, Google, Microsoft
  • D-Wave, uses Quantum annealing to solve optimization problems
• Model of Quantum Computer
  • Input
  • Quantum Processor on Cloud
    • Prepare a state
    • Apply gates
    • Measure
  • Output: the probability distribution of the measurement

2. Classical to Quantum Systems and Basic Quantum Theory

• Quantum Dynamics 量子动力学

  • 时间演化算符
  • 薛定谔方程
  • 哈密顿量
  • 态的演化
  • 量子态的叠加
  • 量子测量

• the state $|\Psi\rangle$ is a superposition of basic state

  • $|\Psi\rangle = c_0|0\rangle + c_1|1\rangle + \cdots + c_n|n\rangle$
  • being simultaneously in all states
  • detect the state with probability $x_i = \frac{|c_i|^2}{\sum_{i=0}^{n} |c_i|^2}$
  • when observed, it will collapse to one of the basic states

• 時間反演對稱

  • $UU^\dagger = I$
  • $U^\dagger U = I$
  • $|\psi\rangle = U|\phi\rangle$
  • $\langle\psi| = \langle\phi|U^\dagger$
  • $\langle\phi|\psi\rangle = \langle\phi|U^\dagger U|\psi\rangle$

• 模不变

  • 量子态的模的表示: $\langle\psi|\psi\rangle$
  • $\langle\psi|\psi\rangle = \langle\phi|U^\dagger U|\phi\rangle = \langle\phi|\phi\rangle$
  • $|\psi\rangle$ 和 $|\phi\rangle$ 的模相等

• 设$\Omega$是一个可观测量，$|\psi\rangle$是一个量子态。如果测量的结果是特征值$\lambda$，则测量后的量子态将始终是对应于$\lambda$的特征向量

• superposition 叠加: $|\psi\rangle \longmapsto \alpha|0\rangle + \beta|1\rangle$

  • $\alpha$ and $\beta$ are complex amplitudes 复振幅
  • an arbitrary state can be represented as a linear combination of basis states

• spin 自旋

  • prototypical way to implement quantum bits of information, or qubits
  • clockwise/anticlockwise

• transition amplitude 转移振幅

  • inner product
  • determine how likely a start state will change to an end state (after measurement)

• entanglement 纠缠

  • connect two qubits using a gate

• Bell state

  • 量子比特间的强纠缠关系
  • $|\Phi^+\rangle = \frac{|00\rangle + |11\rangle}{\sqrt{2}}$
    • 两个量子比特要么都在状态 $|0\rangle$，要么都在状态 $|1\rangle$，且这两种情况的概率相等
    • 最大纠缠态，两个量子比特的状态之间没有相位差，量子态无法分解成两个量子态的直积
  • $|\Phi^-\rangle = \frac{|00\rangle - |11\rangle}{\sqrt{2}}$
    • 两个量子比特的状态之间存在一个相位差
  • $|\Psi^+\rangle = \frac{|01\rangle + |10\rangle}{\sqrt{2}}$
  • $|\Psi^-\rangle = \frac{|01\rangle - |10\rangle}{\sqrt{2}}$

3. Qubits and Quantum Gates

• qubit pair: $|0\rangle \bigotimes |1\rangle$ or $|0 \bigotimes 1\rangle$

  • $\begin{array}{cc} \begin{array}{c} 00 \\ 01 \\ 10 \\ 11\end{array} \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix} \end{array}$

• classical gates

  • NOT: filp 0 to 1, 1 to 0
    • $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$
  • AND: 1 if both are 1
    • $\begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$
  • OR: 1 if either is 1
    • $\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \end{bmatrix}$
  • NAND: 0 if both are 1
    • NOT $\star$ AND
    • $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{bmatrix}$
  • XOR: 1 if either is 1, but not both
    • NOT $\star$ OR
    • $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \end{bmatrix} = \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \end{bmatrix}$

• Jyā, koti-jyā and utkrama-jyā 印度的三角函数

• bloch sphere 布洛赫球: 用于表示量子比特状态的几何图形

  • X, Y axis: $0 \leq \theta \leq 2\pi$
  • Z axis: $0 \leq \phi \leq \frac{\pi}{2}$

• Pauli X,Y,Z

  • $X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$
    • 沿 X 轴旋转 180 度
    • X is also called NOT gate
    • eigenvalues: 1 and -1
    • eigenvectors:
      • left $|\longleftarrow\rangle = \psi_{x+} = \frac{|0\rangle + |1\rangle}{\sqrt{2}}$
      • right $|\longrightarrow\rangle = \psi_{x-} = \frac{|0\rangle - |1\rangle}{\sqrt{2}}$
  • $Y = \begin{bmatrix} 0 & -i \\ i & 0 \end{bmatrix}$
    • 沿 Y 轴旋转 180 度
    • Y is also called bit-flip gate
    • $从|0\rangle$转换为$|1\rangle$，或者从$|1\rangle$转换为$|0\rangle$
    • eigenvalues: 1 and -1
    • eigenvectors:
      • in $|\swarrow\rangle = \psi_{y+} = \frac{|0\rangle + i|1\rangle}{\sqrt{2}}$
      • out $|\nearrow\rangle = \psi_{y-} = \frac{|0\rangle - i|1\rangle}{\sqrt{2}}$
  • $Z = \begin{bmatrix} 1 & 0 \\ 0 & -1 \end{bmatrix}$
    • 沿 Z 轴旋转 180 度
    • Z is also called phase-flip gate
    • 从$|1\rangle$转换为$-|1\rangle$
    • eigenvalues: 1 and -1
    • eigenvectors:
      • up $|\uparrow\rangle = \psi_{z+} = |0\rangle$
      • down $|\downarrow\rangle = \psi_{z-} = |1\rangle$

• phase shift gate:

  • $R(\theta) = \begin{bmatrix} 1 & 0 \\ 0 & e^{\theta} \end{bmatrix}$
  • $R_x(\theta) = \begin{bmatrix} \cos(\frac{\theta}{2}) & -i\sin(\frac{\theta}{2}) \\ -i\sin(\frac{\theta}{2}) & \cos(\frac{\theta}{2}) \end{bmatrix}$
  • $R_y(\theta) = \begin{bmatrix} \cos(\frac{\theta}{2}) & -\sin(\frac{\theta}{2}) \\ \sin(\frac{\theta}{2}) & \cos(\frac{\theta}{2}) \end{bmatrix}$
  • $R_z(\theta) = \begin{bmatrix} e^{-i\frac{\theta}{2}} & 0 \\ 0 & e^{i\frac{\theta}{2}} \end{bmatrix}$

• S: 添加一个 $\frac{\pi}{2}$ 的相位

  • $S = \begin{bmatrix} 1 & 0 \\ 0 & i \end{bmatrix}$

• T: 添加一个 $\frac{\pi}{4}$ 的相位

  • $T = \begin{bmatrix} 1 & 0 \\ 0 & e^{i\frac{\pi}{4}} \end{bmatrix}$

• Hadamard gate

  • 制备叠加态
  • $H = \frac{1}{\sqrt{2}}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$

• CNOT

  • control qubit, target qubit
  • if control qubit is 1, then target qubit is flipped
  • $|00\rangle \longmapsto |00\rangle$
  • $|01\rangle \longmapsto |01\rangle$
  • $|10\rangle \longmapsto |11\rangle$
  • $|11\rangle \longmapsto |10\rangle$
  • $|\psi\rangle = \alpha|00\rangle + \beta|01\rangle + \gamma|10\rangle + \delta|11\rangle$
  • $CNOT = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}$
  • $|\psi'\rangle = CNOT \cdot |\psi\rangle = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} \alpha \ \beta \ \gamma \ \delta \end{bmatrix} = \begin{bmatrix} \alpha \ \beta \ \delta \ \gamma \end{bmatrix}$
  • $|\psi'\rangle = \alpha|00\rangle + \beta|01\rangle + \delta|10\rangle + \gamma|11\rangle$

• control-U gates

  • if control qubit is 1, then apply U on target qubit
  • $^{C}{U} = \begin{bmatrix} I & 0 \\ 0 & U \end{bmatrix}$

• Deutch gate:

  • if both control qubits are 1, then apply a phase shift on target

• Toffoli gate: 3 qubits, 2 control and 1 target

  • if both control qubits are 1, then the target qubit is flipped
  • $\begin{array}{} \ 000 \ 001 \ 010 \ 011 \ 100 \ 101 \ 110 \ 111 \\ \begin{array}{c} 000 \\ 001 \\ 010 \\ 011 \\ 100 \\ 101 \\ 110 \\ 111 \end{array} \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{bmatrix} \end{array}$

• Fredkin gate: 3 qubits, 1 control and 2 target

  • if the control qubit is 1, then the target qubits are swapped
  • $\begin{array}{} \ 000 \ 001 \ 010 \ 011 \ 100 \ 101 \ 110 \ 111 \\ \begin{array}{c} 000 \\ 001 \\ 010 \\ 011 \\ 100 \\ 101 \\ 110 \\ 111 \end{array} \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} \end{array}$

• all Quantum gates are reversible

4. Quantum Circuits

• n Hadamand gates: $H^{\bigotimes n}$

  • $|\psi\rangle = \frac{1}{\sqrt{2^n}}\sum_{i=0}^{2^n-1}|i\rangle$

• reversible function execution:

  • control: $|x\rangle$ --> $U_f$ --> $|x\rangle$
  • target: $|0\rangle$ --> $U_f$ --> $|f(x)\rangle$

• simple circuit

  • CNOT: dot +
  • CZ: dot dot
  • SWAP: xx
  • unitary: box U

• no-cloning theorem: cannot copy an arbitrary unknown quantum state

  • 证明：假设可以复制，那么可以通过两个相同的量子比特，得到一个新的固定的量子比特。但这是不可能的

• teleportation

  • 克隆是在不破坏原本的量子比特的情况下复制一个量子比特
  • 传输是将一个量子比特的状态从一个量子比特传输到另一个量子比特，原本的量子态会被破坏
  • take $|\psi\rangle$ in first system and nothing in second system, then teleport $|x\rangle$ to second system
  • $T(|\psi\rangle \bigotimes |0\rangle) = |\psi\rangle \bigotimes |0\rangle$

• superdense coding

  • teleportation in reverse

• quantum parallelism: exponential numbers were inputted simultaneously, result was given in next clock, by quantum function

• given a quantum representation, only one result can be given, not all solutions

• the point is: what algorithm can take advantage of quantum mechanism?

5. NP Problems, Simulated Annealing and QUBO

• quadratic unconstrained binary optimization 二次无约束二元优化
• quantum mechanics can solve combinatorial optimization problems
  • finding optimal objects that satisfy a certain condition
• Knapsack problem
  • given a set of items, each with a weight and a value
  • determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible
  • n items
  • $x_i$ is 1 if the item is included, 0 otherwise
  • $v_i$ is the value of the item
  • $W$ is the maximum weight
  • maximize $\sum_{i=1}^{n} v_i x_i$
  • subject to $\sum_{i=1}^{n} w_i x_i \leq W$
• max-cut
  • edges have weights
  • find a cut that maximizes the sum of the weights of the edges that are cut
• minimum vetec cover
  • find the minimum number of vertices that cover all edges
• simulated annealing 模拟退火
  • a probabilistic technique for approximating the global optimum of a given function
• local search (Monte Carlo)
  • find solution from neighbors
• Metropolis algorithm
  • reproduce annealing process
  • $E_i$ is the energy of state $i$
  • if $E_i - E_j > 0$, change current state to state $j$
  • if $E_i - E_j < 0$, change current state to state $j$ with probability $e^{\frac{E_i - E_j}{K_b T}}$
• quadratic unconstrained binary optimization (QUBO)
  • $min \ or \ max \sum_{i=1}^{n} \sum_{j=1}^{n} q_{ij} x_i x_j$
  • subject to $x_i \in \{0, 1\}$
  • $Y = X^T Q X$
  • Q is symmetric or upper triangular
  • NP problem

6.1. Ising Hamiltonian and Quantum Adiabatic Annealing

• physical system generates optimal solution
  • map optimization problem to physical system ... cool the system to zero ... obtain the lowest energy state
  • an observable is represented by Hermitian matrix ... its eigenvalues are the measured values ... diagonalize the matrix and eigenvalues are the diagonal elements
• Adiabatic theorem
  • if a system is in the ground state of a Hamiltonian, and the Hamiltonian is slowly changed, then the system will remain in the ground state

6.2. QAOA

• quantum approximate optimization algorithm 量子近似优化算法

Ask GPT

A gpt's explaination of QAOA:

量子近似优化算法（Quantum Approximate Optimization Algorithm，QAOA）是一种混合量子经典算法，用于解决组合优化问题。QAOA 结合了量子计算的并行性和经典优化的灵活性，旨在找到近似最优解。以下是 QAOA 的高层次解释：

QAOA 的基本概念

QAOA 通过构造一个参数化的量子电路来近似求解组合优化问题。该算法的核心思想是通过调整参数，使得量子电路生成的量子态在测量后能够提供优化问题的近似最优解。

QAOA 的步骤

1. 问题表示：

   • 将组合优化问题表示为一个二次无约束二进制优化（QUBO）问题或等价的 Ising 模型。
   • 目标是找到一个二进制向量 $\mathbf{x}$，使得目标函数 $C(\mathbf{x})$ 最小化。

2. 初始量子态：

   • 准备一个初始量子态，通常是所有量子比特的均匀叠加态 $|+\rangle^{\otimes n}$，其中 $n$ 是问题的变量数。

3. 参数化量子电路：

   • 构造一个参数化的量子电路，该电路由两个交替应用的单元组成：
     • 成本哈密顿量演化：应用与目标函数 $C(\mathbf{x})$ 对应的成本哈密顿量 $H_C$。
     • 混合哈密顿量演化：应用混合哈密顿量 $H_M$，通常是所有量子比特上的 Pauli-X 门的和。
   • 这些单元交替应用 $p$ 次，形成一个深度为 $p$ 的量子电路。每个单元的演化时间由参数 $\gamma_i$ 和 $\beta_i$ 控制。

4. 量子态演化：

   • 初始量子态通过参数化量子电路演化，生成一个新的量子态：

     $$|\psi(\gamma, \beta)\rangle = U_M(\beta_p) U_C(\gamma_p) \cdots U_M(\beta_1) U_C(\gamma_1) |+\rangle^{\otimes n}$$

   • 其中 $U_C(\gamma_i) = e^{-i \gamma_i H_C}$ 和 $U_M(\beta_i) = e^{-i \beta_i H_M}$。

5. 测量和优化：

   • 对演化后的量子态进行测量，得到一个二进制向量 $\mathbf{x}$。
   • 计算目标函数 $C(\mathbf{x})$ 的值。
   • 使用经典优化算法调整参数 $\gamma$ 和 $\beta$，以最小化目标函数的期望值 $\langle \psi(\gamma, \beta) | H_C | \psi(\gamma, \beta) \rangle$。

6. 迭代：

   • 重复量子态演化、测量和参数优化的过程，直到找到近似最优解。

QAOA 的优点

• 并行性：利用量子计算的并行性，可以同时探索多个解空间。
• 灵活性：通过调整参数，可以适应不同的优化问题。
• 近似最优解：即使在量子计算资源有限的情况下，QAOA 也能找到高质量的近似解。

QAOA 的应用

QAOA 可以应用于各种组合优化问题，包括但不限于：

• 最大割问题（Max-Cut）
• 旅行商问题（TSP）
• 图着色问题
• 集合覆盖问题
• 资源分配问题

7.1. Quantum Key Distribution

• Alice and Bob agree in advance a set with two different basis, say the z-basis or the x-basis
• Alice sends encoded qubits to Bob using random basis each time
• Bob measures these qubits using random basis
• A qubit sent and received correctly if the basis match. They use this fact to arrive at common correctly received bits
• But how do they discover correct matching?
  • They can announce the basis after the process, they determine which positions of the key has same basis.
• How do they know Eve has not read?
  • They can compare on a subset of qubits, if their recovered bits are same in all bits in the subset then can conclude that Eve was not there. They can use the rest of bits as a shared key.

7.2. Quantum Fourier Transform

• DFT (Discrete Fourier Transform)
  • map vectors from time domain to frequency domain
• periodic function

8. RSA and Shor Algorithms

• story of cryptography

  • Alice, Eve, Bob

• operators: $\oplus$, $\otimes$

  • $x \oplus_n y = (x + y) \mod n$
  • $x \otimes_n y = (xy) \mod n$

• modular inverse

  • if $x \otimes_n y = 1$, then $y$ is the modular inverse of $x$
  • $y$ usually denoted as $x^{-1}$

• Euler's totient function / Euler's phi function

  • a,b are relatively prime if $\gcd(a, b) = 1$
  • $\phi(n)$ is the number of positive integers less than n that are relatively prime to n
  • reduced set of residues is a set that contains all numbers less than n that are relatively prime to n
  • $\phi(p) = p - 1$, where p is a prime number
  • $\phi(pq) = (p - 1)(q - 1)$, where p and q are prime numbers

• RSA PKC

  • Ron Rivest, Adi Shamir, Leonard Adleman public key cryptography
  • utilize modular exponentiation
  • parameter set $K = (n, p, q, e, d)$
    • $n = pq$, where $p$ and $q$ are large prime numbers
    • $e \in (1, \phi(n))$ is a random number
    • $ed \equiv 1 \mod \phi(n)$, where $\phi(n)$ called Euler's totient function
    • $\equiv$ 同余，在模下相等
    • public: $(n, e)$
    • Alice: $E_k(x) = x^e \mod n$
    • Bob: $D_k(y) = y^d \mod n$
    • $(x^e)^d \mod n = x$
  • 证明如果 $ed \equiv 1 \mod \phi(n)$，则$x^{ed} \mod n = x$
    • $ed = k\phi(n) + 1$
    • 费马小定理/欧拉定理: 如果x,n互质，则$x^{\phi(n)} \equiv 1 \mod n$
      • 证明1: $\prod_{i=1}^{p-1} A_i \equiv \prod_{i=1}^{p-1} aA_i \mod p$, 当p是质数，a不是p的倍数时成立。因为两边的p-1个数里都有p-1种可能的余数，两边实际等价的
      • 证明2: $a^{p-1} = (1 + a - 1)^{p-1}$，展开后，除了第一项，其他项都是$p$的倍数，所以等于1

• period of modular exponentiation

  • $f(x) = a^x \mod N$
  • $f(x) = f(x + r)$
  • $f(x) = f(x + r) = f(x + 2r) = \cdots = f(x + kr)$
  • example: $f_{2,15} = 2^x \mod 15$

  x	0	1	2	3	4	5	6	7	8
  f	1	2	4	8	1	2	4	8	1

• bit needed to represent $N$

  • $n \geq \log_2 N$ in binary
  • because $2^n \geq N$

• Shor's algorithm

  • use quantum circuit to find period of big N
  • let $0_m$, $0_n$ be the input strings, where $m = 2n$ and $n = \log_2 N$
  • input: $|\psi_0\rangle = |0_m0_n\rangle$
  • pass through m Hadamard gates $H^{\bigotimes m}$: $|\psi_1\rangle = \frac{1}{\sqrt{2^m}}\sum_{x \in [0,1]^m}|x, 0_n\rangle$
  • pass through unitary operator $U_f$: $|\psi_2\rangle = \frac{1}{\sqrt{2^m}}\sum_{x \in [0,1]^m}|x, f_{a, N}(x)\rangle$
  • the bottom n qubits store the superposition of many states $a^x \mod N$, measure and collapse: $|\psi_3\rangle = \frac{1}{\lfloor \frac{2^m}{r} \rfloor}\sum_{a^x \equiv a^{\bar{x}} \mod N}|x, a^{\bar{x}} \mod N\rangle$
  • apply quantum Fourier transform (QFT) on the top m qubits to generate answer: r

9. Quantum Machine Learning

...