2026-06-12
Notes taken from course Theory of Computation.
Simple notations that could be obtained from Concrete Quantum Mechanics are omitted.
Some \(|\rangle\) for kets are omitted for convenience, with bras replaced by \(\dagger\).
Superposition: for \(n\) qubits superposition, the space is identical to \(C^N\), \(N=2^n\).
Quantum operation: each quantum operation is a unitary matrix over \(C^{N\times N}\).
Mixed state: a convex combination of superpositions, \(\{p_i,\phi_i\}\).
- The density of such system is defined by the matrix \(\rho=\sum_i p_i|\phi_i\rangle\langle \phi_i|\).
- Could easily obtain that the mixed state after quantum operation \(U\) changes to \(U\rho U^{\dagger}\).
Single-bit operation examples:
- Pauli matrices \(X,Y,Z\).
- Hadamard gate \(H\), phase gate \(S\), \(\pi/8\) gate \(T\).
Quantum measurement:
In short, a measurement project the whole state space into a subspace.
In details, measurement is described by a collection \(\{M_m\}\) of measurement operators.
The probability of that result \(m\) occurs is \(\langle \phi|M^{\dagger}_m M_m |\phi\rangle\), and the state after the measurement is \(\frac{M_m|\phi\rangle}{\sqrt{p(m)}}\).
It should be satisfied that \(\sum_m M_m^{\dagger} M_m=I\).
Define \(E_m:=M_m^{\dagger}M_m\). The set \(\{E_m\}\) is known as the POVM of the measurement.
Projective measurement:
In short, project measurement force the result to be eigenspace of \(M\) and \(M\) to be Hermitian.
\(M\) is a Hermitian operator with \(M=\sum_m mP_m\), where \(P_m\) is rhe projector onto the eigenspace of \(M\) with eigenvalue \(m\).
Thus, the probability of getting result \(m\) is \(p_m=\langle \phi | P_m \phi \rangle\), with the state after measurement being \(\frac{P_m|\phi\rangle}{\sqrt{p(m)}}\).
Quantum Turing Machine:
For input size \(n\) and time \(T(n)\), find a polynomial-time classical TM with \((1^n,1^{T(n)})\) that outputs the description of quantum gates \(F_i\) (in other words, uniform).
Function \(f(x)\) could be computed by the following probability with at least \(2/3\) accuracy:
- Initialize m-qubit quantum register to the state \(x0^{m-n}\).
- Apply \(T(n)\) quantum operators one after another.
- Measure the register by projecting it to the standard basis. Let \(Y\) be the obtained value. Output \(Y_i\).
BQP: P-time using QTM.
(Note: It is proven that QIP=IP=PSPACE. However, quantum advantage could also be seen in interactive proof)
eg. BPP in BQP. Simply generate the random string using quantum measurement.
Grover Search:
Theorem: There exists a quantum algo, that given as input every poly-time computable function \(f\), finds in \(poly(n)2^{n/2}\) time a string \(a\) such that \(f(a)=1\) if such string exists.
Assume \(f\) only got one satisfying assignment. Also, the \(f\) gives us an quantum operation \(O\): \(xq\to x(q\oplus f(x))\). (rangle is omitted for \(x,q\))
Algo:
Attain \(u=\frac{1}{2^{n/2}}\sum_{x\in \{0,1\}^n} x\) (which serves as uniform distribution of all possible answers)
\(u=H^{\otimes n}(0^{\otimes n})\).
Notice that the inner product of \(u,a=1/2^{n/2}\). Denote such angle as \(\pi/2-\theta\), hence \(\sin\theta=1/2^{n/2}\).
Start with \(u\), and repeat for \(O(1/\theta)=O(2^{n/2}\) steps. Each step shrink the angle from \(\pi/2-\alpha\) to \(\pi/2-\alpha-2\theta\).
Step 1: Reflect \(x\) around direction \(e\) (orth against \(a\)).
Use \(O\) with \(q=\frac{0-1}{\sqrt 2}\), and transform \(x\to (-1)^{f(x)}x\).
Step 2: Reflect \(x\) around \(u\) (namely, the grover diffusion operator).
We want to obtain \(x\to (2u^{\dagger} u-I)x\). The question is how to construct such operator.
\(2u^\dagger u-I=H^n\left(\begin{matrix} 1 & \\ & diag^{2^n-1}(-1) \end{matrix}\right) H^n\) .
The center matrix could be constructed as: calculate the OR of all bits as \(r\), and CNOT with \(r\).