Arthur (verifier) is a computational entity, typically represented as a Turing Machine, thus having bounded capabilities. Arthur's job is to verify the solutions for a given decision problem using the proof/witness state provided by Merlin (prover). Based on certain criterion, Arthur will accept or reject with some probability.
Merlin
Merlin (prover) exists as an omniscient, omnipotent and mendacious entity, having unbounded computational resources — essentially representing an infinitely powerful oracle. Additionally, Merlin possesses the ability to generate quantum states. The role of Merlin is to convince Arthur (verifier) as to the validity of a decision problem's solution via some proof/witness state.
Polynomial Time
In computational theory, a polynomial time algorithm is an algorithm whose running time is bounded by a polynomial function of the input size. More formally, an algorithm is said to run in polynomial time if there exists a polynomial function $f(n)$, where $n$ represents the size of the input, such that the algorithm's running time is $O\big(f(n)\big)$.
Quantum Computer
A quantum computer is a computational machine that utilises the fundamental principles of quantum mechanics to execute computation tasks. The primitive elements of a quantum computer are quantum bits (qubits) — naturally exhibiting superposition and entanglement properties. Their attributes generate the quantum advantage in information processing not efficiently produced on classical computers.
Reduction (From)
A reduction 'From' one problem $A$, to a problem $B$, refers to reducing (in polynomial time) or perhaps relaxing conditions on problem $A$ to produce problem $B$. Informally, this can be understood as $B\subseteq A$, where $A$ is the parent problem we reduce from to obtain $B$.
Reduction (To)
A reduction 'To' one problem $Y$, from a problem $X$, refers to reducing (in polynomial time) or perhaps relaxing conditions on problem $X$ to produce problem $Y$. Informally, this can be understood as $Y\subseteq X$, where $Y$ is the child problem we reduce to from $X$.
Isotropic Antiferromagnetic (IaF)
An isotropic antiferromagnetic Hamiltonian is one such that each present interaction term, $J_{ij}, K_{ij}, \ldots$ is of the form $J_{ij} \geq 0$. Antiferromagnetism refers to the non–negative interaction strength sector. The isotropic labeling refers to the fact that all interaction terms adhere to the positive weight restriction but do not necessarily all have the same value. Isotropic Ferromagnetic is the analogous non–positive regime.
Homogeneous Antiferromagnetic (HaF)
A homogeneous antiferromagnetic Hamiltonian is one such that all present interaction terms, $J_{ij}, K_{ij}, \ldots$ are different but fixed non–negative values for all particle interactions. Antiferromagnetism refers to the non–negative interaction strength sector. The homogeneous labeling refers to the fact that all interaction terms between particles are now some constant non–negative value. Homogeneous Ferromagnetic is the analogous non–positive regime.
Local Hamiltonian Problem
Given a $k=O(1)$ local Hamiltonian, $H$, acting on an $n$–qubit system, such that, $$H = \sum_{j=1}^m H_j$$ where $||H_j||\leq\mathsf{poly}(n)$, each element of every $H_j$ can be specified in $\mathsf{poly}(n)$ bits and $m\leq\mathsf{poly}(n)$, the problem statement is to determine which of the following is true, promised one is so:
The smallest eigenvalue of $H$ is $\leq a$
All eigenvalues of $H$ are $\geq b$
Commuting Local Hamiltonian Problem
Given a $k=O(1)$ local Hamiltonian, $H$, acting on an $n$–qudit system, such that, $$H = \sum_{j=1}^m h_j$$ where $[h_j,h_k]=0$ for all $j,k$ and with $||H_j||\leq\mathsf{poly}(n)$, each element of every $H_j$ can be specified in $\mathsf{poly}(n)$ bits and $m\leq\mathsf{poly}(n)$, the problem statement is to determine which of the following is true, promised one is so:
The smallest eigenvalue of $H$ is $\leq a$
All eigenvalues of $H$ are $\geq b$
(This can be reformulated in terms of a projectors which then asks if the ground space is of positive dimension)
Max–Cut
Given a graph $G=(V,E,w_{ij})$, where $w_{ij} \geq 0$ is the weight of the edge between vertices $i$ and $j$, compute the maximum eigenvalue of the Hamiltonian $$H_{MC}(G) = \frac{1}{2} \sum_{\{i,j\} \in E(G)} w_{ij} \left(\mathbb{I} - S_i \cdot S_j\right)$$ Subject to $S_i \in \{\pm 1\}$.
$W$–Linear–Max–Cut
Given a graph $G=(V,E)$ and a fixed $d\times d$ matrix $W$, assign unit vectors to maximise the following: $$MC_W^L(G) = \frac{1}{2} \displaystyle\max_{i\in S^{d-1}} \displaystyle\sum_{\{i,j\}\in E(G)} ||Wi - Wj||$$
Quantum Max–Cut
Given a graph $G=(V,E,w_{ij})$, where $w_{ij} \geq 0$ is the weight of the edge between vertices $i$ and $j$, compute the maximum eigenvalue of the Hamiltonian $$H_{QMC_S}(G) = \frac{1}{2} \sum_{\{i,j\} \in E(G)} w_{ij} \left(\mathbb{I} - \frac{1}{S^2}\;\boldsymbol{S}_i \cdot \boldsymbol{S}_j \right)$$ (This is the standard definition where each edge is a singlet state)
Quantum Max–Cut(EPR)
Given a graph $G=(V,E,w_{ij})$, where $w_{ij} \geq 0$ is the weight of the edge between vertices $i$ and $j$, compute the maximum eigenvalue of the Hamiltonian $$H_{QMC(EPR)}(G) = \frac{1}{2} \sum_{\{i,j\} \in E(G)} w_{ij} \left(\mathbb{I} + X_iX_j - Y_iY_j + Z_iZ_j\right)$$ (This is the a variant on the standard Quantum Max–Cut where each edge is an EPR state)
Quantum Partition Function
Given a $k$–local Hamiltonian $H$ on $n$ qubits, an inverse temperature $\beta = O(\mathsf{poly}(n))$ and a precision parameter $\delta = \Omega(1/\mathsf{poly}(n))$, compute an approximation to the partition function $Z(\beta) = \text{Tr}\left[e^{-\beta H}\right]$ such that $$\big| Z - \widetilde{Z}\big| \leq \delta Z.$$
Additive $\varepsilon$–Approximation
Let $a$, $\hat{a}$ and $\varepsilon$ be positive real numbers. We say that $\hat{a}$ is the additive $\varepsilon$-approximation of $a$ if $$ |{a - \hat{a}}| \leq \varepsilon.$$
Multiplicative $\varepsilon$–Approximation
Let $a$, $\hat{a}$ and $\varepsilon$ be positive real numbers. We say that $\hat{a}$ is the multiplicative $\varepsilon$-approximation of $a$ if $$ |{a - \hat{a}}| \leq \varepsilon a.$$
Let $z = re^{i\theta}$ and $\hat{z} = \hat{r}e^{i\hat{\theta}}$. We say that $\hat{z}$ is the multiplicative $\varepsilon$-approximation of $z$ if $$ |{r - \hat{r}}| \leq \varepsilon r \quad \text{and} \quad |{\theta - \hat{\theta}}| \leq \varepsilon.$$
Complexity Theory
See the
Complexity Zoo
for a more comprehensive list of complexity classes.
Polynomial Time — P
A decision problem $L$ is in P if there exists: a deterministic Turing Machine, $M$, such that
For any input $x$, $M$ runs for a time $O(\mathsf{poly}(|x|)\big)$.
For all $x\in L$, $M$ outputs $\mathtt{1}$.
For all $x\notin L$, $M$ outputs $\mathtt{0}$.
Nondeterministic Polynomial —
NP
A decision problem $L$ is in
NP if there exists: a deterministic verification Turing Machine, $M$, and a polynomial, $\mathsf{poly}(|x|)$, such that
For all $x\in L$, $M(x,\mathsf{poly}(|x|))=\mathtt{1}$.
For all $x\notin L$, $M(x,\mathsf{poly}(|x|))=\mathtt{0}$.
A decision problem $L$ is in
BPP($\mathsf{a}$,$\mathsf{b}$) if there exists: a probabilistic Turing Machine, $M$, such that
For any input $x$, $M$ runs for a time $O(\mathsf{poly}(|x|))$.
For all $x\in L$, $\text{Pr}\left[M(x)=\mathtt{1} \right] \geq a$.
For all $x\notin L$, $\text{Pr}\left[M(x)=\mathtt{1} \right] \leq b$.
Randomised Polynomial — RP
A decision problem $L$ is in
RP if there exists: a probabilistic Turing Machine, $M$, such that
For any input $x$, $M$ runs for a time $O(\mathsf{poly}(|x|))$.
For all $x \in L$, $\text{Pr}[M(x) = \mathtt{1}] \geq \frac{1}{2}$.
For all $x \notin L$, $\text{Pr}[M(x) = \mathtt{1}] = 0$.
Merlin–Arthur —
MA($\mathsf{a}$,$\mathsf{b}$)
A decision problem $L$ is in
MA($\mathsf{a}$,$\mathsf{b}$) if there exists: a deterministic verification Turing Machine, $M$, and a polynomial, $\mathsf{poly}(|x|)$, such that
For all $x\in L$, there exists a proof state, $z \in \{0,1\}^{\mathsf{poly}(|x|)}$, such that, $\text{Pr}\left[M(x,z)=\mathtt{1} \right] \geq a$.
For all $x\notin L$, for any proof state, $z \in \{0,1\}^{\mathsf{poly}(|x|)}$, then, $\text{Pr}\left[M(x,\mathsf{poly}(|x|))=\mathtt{1} \right] \leq b$.
Sharp P — #P
The class #P consists of all functions $f:\Sigma^* \rightarrow \mathbb{N}$ for which there exists a polynomial $p:\mathbb{N} \rightarrow \mathbb{N}$ and a polynomial-time algorithm $A$ such that:
for all $x \in \Sigma^*$ $f(x) = |\{y \in \Sigma^{p(x)} : A(x,y)\;\text{accepts} \}|$
GapP — GapP
The class GapP consists of all functions $f:\Sigma^* \rightarrow \mathbb{Z}$ for which there exists a polynomial nondeterministic Turing machine $M$ such that
for all $x \in \Sigma^*$ $f(x) = \#M(x) - \# \bar{M}(x)$
where $\#M(x)$ and $\# \bar{M}(x)$ are the number of accepting and rejector paths of $M$ on $x$.
A fully polynomial-time approximation scheme for a counting problem $f:\Sigma^* \rightarrow \mathbb{N}$ is an algorithm $A$ that takes as input an instance $x \in \Sigma^*$ and a number $\epsilon \gt 0$ and outputs a multiplicative $\epsilon$-approximation to $f(x)$ in polynomial time in $|x|$ and $1/\epsilon$.
A fully polynomial-time randomised approximation scheme for a counting problem $f:\Sigma^* \rightarrow \mathbb{N}$ is an algorithm $A$ that takes as input an instance $x \in \Sigma^*$ and a number $\epsilon \gt 0$ and outputs a multiplicative $\epsilon$-approximation to $f(x)$ with probability at least $2/3$ in polynomial time in $|x|$ and $1/\epsilon$.
A decision problem $L$ is in
BQP($\mathsf{a}$,$\mathsf{b}$) if there exists: a polynomial–time uniform family of quantum circuits, $Q = \{Q_n | n \in \mathbb{N}\}$, such that
$Q_n$ has $n$–qubits as input and $1$ qubit as output.
For all $x\in L$, $\text{Pr}\left[Q(x)=\mathtt{1} \right] \geq a$.
For all $x\notin L$, $\text{Pr}\left[Q(x)=\mathtt{1} \right] \leq b$.
A decision problem $L$ is in
StoqMA($\alpha$,$\beta$) if there exists: a polynomial stoquastic verifier, $V = (n,w,m,p, U)$, such that
$n$ is the number of input bits, $w$, the number of proof qubits, $m$, the number of $\ket{0}$ ancillae and $p$, the number of $\ket{+}$ ancillae.
$U$ is a quantum circuit on $n + w + m +p$ qubits using gates from the set $\{ X$,
Cnot, Toff$\}$.
The acceptance probability of a stoquastic verifier $V$ given some input string $x\in L$ and a proof state $\ket{\psi}$, $\text{Pr}\left[V(x,\ket{\psi})\right]= \bra{\phi}U^\dagger \Pi_{\text{out}} U \ket{\phi}$, where $\ket{\phi} = \ket{x,\psi,0^{m},+^{p}}$ and $\Pi_{\text{out}} = \ketbra{+}{+}_1$.
Completeness: For all $x\in L$, there exists a quantum proof state, $\ket{\psi}\in\mathcal{B}^{w}$, such that, $\text{Pr}\left[V(x,\ket{\psi})=\mathtt{1} \right] \geq \alpha$.
Soundness: For all $x\notin L$, for any quantum proof state, $\ket{\psi}\in\mathcal{B}^{w}$, then, $\text{Pr}\left[V(x,\ket{\psi})=\mathtt{1} \right] \leq \beta$.
Where $\alpha$ refers to the completeness parameter and $\beta$ the soundness parameter, where $-1/2 \leq \beta(n) \lt \alpha(n) \leq 1$ and satisfying $\alpha-\beta\geq\frac{1}{\mathsf{poly}(n)}$.
Quantum Merlin–Arthur —
QMA($c$,$s$)
A promise problem $L$ is in
QMA($c$,$s$) if there exists: a polynomial quantum verifier, $V$, and a polynomial, $\mathsf{poly}(|x|)$, for $x\in L$, such that
Completeness: For all $x\in L$, there exists a quantum proof state, $\ket{\psi}\in\mathcal{B}^{\mathsf{poly}(|x|)}$, such that, $\text{Pr}\left[V(x,\ket{\psi})=\mathtt{1} \right] \geq c$.
Soundness: For all $x\notin L$, for any quantum proof state, $\ket{\psi}\in\mathcal{B}^{\mathsf{poly}(|x|)}$, then, $\text{Pr}\left[V(x,\ket{\psi})=\mathtt{1} \right] \leq s$.