End-to-End Quantum-Kernel SVM

1. 1
   Step 1:

   $$L(w,b,\xi,\alpha,\mu)=\tfrac12\lVert w\rVert^2+C\sum_i\xi_i-\sum_i\alpha_i\big[y_i(\langle w,\varphi(x_i)\rangle+b)-1+\xi_i\big]-\sum_i\mu_i\xi_i,\qquad\alpha,\mu\ge0$$

   Lagrangian with one multiplier $\alpha_i\ge0$ for each margin constraint and one $\mu_i\ge0$ for each $\xi_i\ge0$.
2. 2
   Step 2:

   $$\nabla_wL=w-\sum_i\alpha_iy_i\varphi(x_i)=0\ \Rightarrow\ w=\sum_i\alpha_iy_i\varphi(x_i)$$

   $L$ is a convex quadratic in $w$; its gradient vanishes at the minimiser. The normal vector is a combination of training features, as the representer theorem predicts.
3. 3
   Step 3:

   $$\frac{\partial L}{\partial b}=-\sum_i\alpha_iy_i=0,\qquad\frac{\partial L}{\partial\xi_i}=C-\alpha_i-\mu_i=0\ \Rightarrow\ 0\le\alpha_i=C-\mu_i\le C$$

   $L$ is linear in $b$ and $\xi_i$, so the infimum is $-\infty$ unless these coefficients vanish; $\mu_i\ge0$ turns the second equation into the box constraint.
4. 4
   Step 4:

   $$\Big\lVert\sum_i\alpha_iy_i\varphi(x_i)\Big\rVert^2=\sum_{i,j}\alpha_i\alpha_jy_iy_j\langle\varphi(x_i),\varphi(x_j)\rangle=\sum_{i,j}\alpha_i\alpha_jy_iy_j(K_{\text{train}})_{ij}$$

   Bilinearity of the inner product and the kernel property $\langle\varphi(x_i),\varphi(x_j)\rangle=K(x_i,x_j)$: the feature vectors never appear on their own, only through kernel values.
5. 5
   Step 5:

   $$L=\tfrac12\lVert w\rVert^2-\lVert w\rVert^2-b\sum_i\alpha_iy_i+\sum_i\alpha_i+\sum_i\xi_i(C-\alpha_i-\mu_i)=\sum_i\alpha_i-\tfrac12\sum_{i,j}\alpha_i\alpha_jy_iy_j(K_{\text{train}})_{ij}$$

   Insert the three stationarity conditions: $\sum_i\alpha_iy_i\langle w,\varphi(x_i)\rangle=\lVert w\rVert^2$, the $b$ term and the $\xi$ terms vanish. This is the dual objective.
6. 6
   Step 6:

   $$w=0,\ b=0,\ \xi_i=1\ \text{is feasible}\ \Rightarrow\ \text{primal optimum}=\text{dual optimum}$$

   The primal is a convex quadratic program with affine constraints and a feasible point, so strong duality holds and the KKT conditions are necessary and sufficient for optimality (linear constraint qualification).
7. 7
   Step 7:

   $$f(x)=\langle w,\varphi(x)\rangle+b=\sum_i\alpha_iy_i\langle\varphi(x_i),\varphi(x)\rangle+b=\sum_i\alpha_iy_iK(x_i,x)+b$$

   Insert $w$; at a test point $x^\ast_t$ the kernel values are the entries of row $t$ of $K_{\text{test}}$, so $f=K_{\text{test}}(\alpha\circ y)+b\mathbf 1$ for all test points at once.
8. 8
   Step 8:

   $$\langle\rho(x),\rho(x')\rangle_{HS}=\mathrm{Tr}\big(\rho(x)\rho(x')\big)=K(x,x'),\qquad w=\sum_i\alpha_iy_i\rho(x_i)=:O=O^\dagger$$

   The fidelity kernel is the Hilbert–Schmidt inner product of the encoded density operators (lesson Quantum Kernels & Fidelity Kernels); a real combination of Hermitian matrices is Hermitian, so the trained model is the expectation value of an observable plus a bias.

∎

1. 1
   Step 1:

   $$\alpha_i\big[y_i(\langle w,\varphi(x_i)\rangle+b)-1+\xi_i\big]=0,\qquad\mu_i\xi_i=(C-\alpha_i)\xi_i=0$$

   KKT complementary slackness: a multiplier can be positive only when its constraint is active. The second form uses $\mu_i=C-\alpha_i$ from the previous theorem.
2. 2
   Step 2:

   $$0<\alpha_s<C\ \Rightarrow\ C-\alpha_s>0\ \Rightarrow\ \xi_s=0$$

   A free support vector has $\mu_s>0$, so its slack vanishes: it lies exactly on the margin.
3. 3
   Step 3:

   $$\alpha_s>0\ \Rightarrow\ y_sf(x_s)-1+\xi_s=0\ \Rightarrow\ y_sf(x_s)=1$$

   The margin constraint of $s$ is active and $\xi_s=0$.
4. 4
   Step 4:

   $$y_s^2=1\ \Rightarrow\ f(x_s)=y_s\ \Rightarrow\ \sum_i\alpha_iy_i(K_{\text{train}})_{is}+b=y_s\ \Rightarrow\ b=y_s-\sum_i\alpha_iy_i(K_{\text{train}})_{is}$$

   Multiply $y_sf(x_s)=1$ by $y_s$ and insert the decision function of the previous theorem at the training point $x_s$.
5. 5
   Step 5:

   $$\alpha_i=0\ \Rightarrow\ \xi_i=0\ \Rightarrow\ y_if(x_i)\ge1;\qquad\alpha_i=C\ \Rightarrow\ y_if(x_i)=1-\xi_i\le1$$

   For $\alpha_i=0$, $\mu_i=C>0$ forces $\xi_i=0$ and primal feasibility gives $y_if(x_i)\ge1$; for $\alpha_i=C$ the margin constraint is active with $\xi_i\ge0$.
6. 6
   Step 6:

   $$b_s=b_{s'}\ \ \forall s,s'\in S\ \Rightarrow\ \frac1{\lvert S\rvert}\sum_{s\in S}b_s=b$$

   In exact arithmetic every free support vector yields the same value; an iterative solver stops at a tolerance, and averaging the $b_s$ reduces the effect of the residual KKT violations. LIBSVM, behind scikit-learn's SVC, uses this average (and the midpoint of the feasible interval of $b$ when $S$ is empty).

∎

1. 1
   Step 1:

   $$\mathrm{CNOT}_{01}\lvert q_0q_1\rangle=\lvert q_0,\,q_0\oplus q_1\rangle,\qquad\mathrm{CNOT}_{01}^2=I$$

   The CNOT flips the target exactly when the control is $1$; applying it twice adds $q_0$ twice modulo $2$, which is the identity.
2. 2
   Step 2:

   $$\big(I\otimes P(\lambda)\big)\lvert q_0,\,q_0\oplus q_1\rangle=e^{i\lambda(q_0\oplus q_1)}\lvert q_0,\,q_0\oplus q_1\rangle$$

   $P(\lambda)\lvert b\rangle=e^{i\lambda b}\lvert b\rangle$ for $b\in\{0,1\}$, here applied to the target bit $b=q_0\oplus q_1$.
3. 3
   Step 3:

   $$\mathrm{CNOT}_{01}\big(I\otimes P(\lambda)\big)\mathrm{CNOT}_{01}\lvert q_0q_1\rangle=e^{i\lambda(q_0\oplus q_1)}\,\mathrm{CNOT}_{01}\lvert q_0,\,q_0\oplus q_1\rangle=e^{i\lambda(q_0\oplus q_1)}\lvert q_0q_1\rangle$$

   Linearity pulls the scalar out; the second CNOT undoes the first because $q_0\oplus(q_0\oplus q_1)=q_1$.
4. 4
   Step 4:

   $$(q_0\oplus q_1)_{q=00,01,10,11}=(0,1,1,0)\ \Rightarrow\ \mathrm{diag}(1,e^{i\lambda},e^{i\lambda},1)$$

   The operator is diagonal in the computational basis, ordered $\lvert00\rangle,\lvert01\rangle,\lvert10\rangle,\lvert11\rangle$.
5. 5
   Step 5:

   $$(Z\otimes Z)\lvert q_0q_1\rangle=(-1)^{q_0}(-1)^{q_1}\lvert q_0q_1\rangle=(-1)^{q_0\oplus q_1}\lvert q_0q_1\rangle,\qquad q_0\oplus q_1=\frac{1-(-1)^{q_0\oplus q_1}}2$$

   $Z\lvert b\rangle=(-1)^b\lvert b\rangle$, and $(-1)^{q_0+q_1}=(-1)^{q_0\oplus q_1}$ since only the parity of the exponent matters; the second identity checks on the two parities $0$ and $1$.
6. 6
   Step 6:

   $$e^{i\lambda(q_0\oplus q_1)}=e^{i\lambda/2}\,e^{-i\frac\lambda2(-1)^{q_0\oplus q_1}}\ \Rightarrow\ \mathrm{diag}(1,e^{i\lambda},e^{i\lambda},1)=e^{i\lambda/2}\exp\Big(-i\frac\lambda2Z\otimes Z\Big)$$

   Insert the parity identity. A function of a diagonal matrix acts entrywise on its eigenvalues, so $\exp(-i\frac\lambda2Z\otimes Z)$ has the eigenvalue $e^{-i\frac\lambda2(-1)^{q_0\oplus q_1}}$ on $\lvert q_0q_1\rangle$.

∎

1. 1
   Step 1:

   $$(H\otimes H)\lvert00\rangle=\lvert{+}\rangle\otimes\lvert{+}\rangle=\frac12\big(\lvert00\rangle+\lvert01\rangle+\lvert10\rangle+\lvert11\rangle\big)$$

   $H\lvert0\rangle=\frac1{\sqrt2}(\lvert0\rangle+\lvert1\rangle)$ on each qubit; expand the tensor product.
2. 2
   Step 2:

   $$P_0(2x_0)P_1(2x_1)\lvert q_0q_1\rangle=e^{2i(x_0q_0+x_1q_1)}\lvert q_0q_1\rangle$$

   Each phase gate multiplies by $e^{i\lambda b}$ where $b$ is the bit of its own qubit.
3. 3
   Step 3:

   $$\mathrm{CNOT}_{01}P_1(2\varphi_{01})\mathrm{CNOT}_{01}\lvert q_0q_1\rangle=e^{2i\varphi_{01}(q_0\oplus q_1)}\lvert q_0q_1\rangle$$

   The lemma with $\lambda=2\varphi_{01}$.
4. 4
   Step 4:

   $$\theta_q=2x_0q_0+2x_1q_1+2\varphi_{01}(q_0\oplus q_1):\quad\theta_{00}=0,\ \theta_{01}=2x_1+2\varphi_{01},\ \theta_{10}=2x_0+2\varphi_{01},\ \theta_{11}=2x_0+2x_1$$

   All gates after the Hadamards are diagonal, so their phases add on each basis state of the uniform superposition; $1\oplus1=0$ removes the product phase from $\lvert11\rangle$.
5. 5
   Step 5:

   $$q_j=\frac{1-z_j}2,\ \ q_0\oplus q_1=\frac{1-z_0z_1}2\ \Rightarrow\ \theta_q=(x_0+x_1+\varphi_{01})-(x_0z_0+x_1z_1+\varphi_{01}z_0z_1)$$

   $z_j=(-1)^{q_j}$ is the eigenvalue of $Z_j$ on $\lvert q\rangle$. Hence the diagonal phase operator equals $e^{i(x_0+x_1+\varphi_{01})}\exp\big(-i(x_0Z_0+x_1Z_1+\varphi_{01}Z_0Z_1)\big)$, which acting on $\lvert{+}{+}\rangle$ gives the exponential form.
6. 6
   Step 6:

   $$\langle\phi(x)\vert\phi(x')\rangle=\frac14\sum_q\overline{e^{i\theta_q(x)}}\,e^{i\theta_q(x')}=\frac14\sum_qe^{i(\theta_q(x')-\theta_q(x))}$$

   Inner product antilinear in the first argument, computed in the orthonormal computational basis.
7. 7
   Step 7:

   $$K(x,x')=\frac1{16}\Big\lvert\sum_qe^{i(\theta_q(x')-\theta_q(x))}\Big\rvert^2,\qquad K(x,x)=\frac{\lvert4\rvert^2}{16}=1$$

   Square the modulus. The diagonal check confirms normalisation; four phases can cancel completely, so $K$ ranges over all of $[0,1]$.

∎

1. 1
   Step 1:

   $$R_Z(\lambda)=\begin{pmatrix}e^{-i\lambda/2}&0\\0&e^{i\lambda/2}\end{pmatrix}=e^{-i\lambda/2}\begin{pmatrix}1&0\\0&e^{i\lambda}\end{pmatrix}=e^{-i\lambda/2}P(\lambda)$$

   Factor $e^{-i\lambda/2}$ out of both diagonal entries.
2. 2
   Step 2:

   $$R_Z(2x_0)\otimes R_Z(2x_1)=e^{-ix_0}e^{-ix_1}\,P(2x_0)\otimes P(2x_1)$$

   The Kronecker product is bilinear, so scalar factors of the two operands multiply.
3. 3
   Step 3:

   $$\mathrm{CNOT}_{01}\big(I\otimes R_Z(2\varphi_{01})\big)\mathrm{CNOT}_{01}=e^{-i\varphi_{01}}\,\mathrm{CNOT}_{01}\big(I\otimes P(2\varphi_{01})\big)\mathrm{CNOT}_{01}$$

   Same factorisation with $\lambda=2\varphi_{01}$, pulled out of the matrix product by linearity.
4. 4
   Step 4:

   $$U_{R_Z}(x)=e^{-i(x_0+x_1+\varphi_{01})}\,U_P(x),\qquad\big(e^{-i\alpha}U_P\big)^r=e^{-ir\alpha}U_P^r$$

   A scalar multiple of the identity commutes with every matrix, so all phases collect in front of one repetition $U_P(x)$ of the phase-gate circuit, and $r$ repetitions collect $r$ copies.
5. 5
   Step 5:

   $$r=1:\ \lvert\phi_{R_Z}(x)\rangle=e^{-i(x_0+x_1+\varphi_{01})}e^{i(x_0+x_1+\varphi_{01})}\exp\big(-i(x_0Z_0+x_1Z_1+\varphi_{01}Z_0Z_1)\big)\lvert{+}{+}\rangle$$

   Insert the exponential form of the closed-form proposition; the two phases cancel, leaving the Havlíček form $U_\Phi(x)H^{\otimes2}\lvert00\rangle$ with $U_\Phi(x)=\exp\big(-i\sum_S\phi_S(x)\prod_{j\in S}Z_j\big)$.
6. 6
   Step 6:

   $$K_{R_Z}(x,x')=\big\lvert\langle e^{-i\beta(x)}\phi(x)\vert e^{-i\beta(x')}\phi(x')\rangle\big\rvert^2=\big\lvert e^{i(\beta(x)-\beta(x'))}\big\rvert^2\,\lvert\langle\phi(x)\vert\phi(x')\rangle\rvert^2=K(x,x')$$

   With $\beta=r(x_0+x_1+\varphi_{01})$: the bra conjugates its phase, and a unimodular factor drops out of the modulus. Data-dependent global phases are invisible to the fidelity kernel (lesson Quantum Kernels & Fidelity Kernels).

∎

1. 1
   Step 1:

   $$K_s(u,u')=\prod_{j}\cos^2\frac{su_j-su'_j}{2}=\prod_j\cos^2\frac{s\Delta_j}2$$

   Product-encoding kernel of the lesson Quantum Kernels & Fidelity Kernels, evaluated at the scaled features $su$ and $su'$.
2. 2
   Step 2:

   $$g(t)=\ln\cos t+\frac{t^2}2,\quad g(0)=0,\quad g'(t)=-\tan t+t\le0\quad(0\le t<\tfrac\pi2)$$

   $\tan t\ge t$ on $[0,\frac\pi2)$ because $\tan t-t$ vanishes at $0$ and has derivative $\tan^2t\ge0$. Hence $g$ is non-increasing and $\ln\cos t\le-\frac{t^2}2$.
3. 3
   Step 3:

   $$t=\frac{s\lvert\Delta_j\rvert}2<\frac\pi2:\quad\cos^2\frac{s\Delta_j}2=e^{2\ln\cos t}\le e^{-t^2}=e^{-s^2\Delta_j^2/4}$$

   $\cos$ is even, so $\lvert\Delta_j\rvert$ may replace $\Delta_j$. At $t=\frac\pi2$ the left side is $0$ and the inequality holds trivially.
4. 4
   Step 4:

   $$K_s(u,u')\le\prod_je^{-s^2\Delta_j^2/4}=\exp\Big(-\frac{s^2}4\sum_j\Delta_j^2\Big)=\exp\Big(-\frac{s^2}4\lVert\Delta\rVert^2\Big)$$

   Multiply the $d$ non-negative inequalities; this is (a).
5. 5
   Step 5:

   $$\cos^2\frac{t}2=\frac{1+\cos t}2=1-\frac{t^2}4+\frac{t^4}{48}-\cdots\ \Rightarrow\ \prod_j\Big(1-\frac{s^2\Delta_j^2}4+O(s^4\Delta_j^4)\Big)=1-\frac{s^2}4\lVert\Delta\rVert^2+O(s^4\lVert\Delta\rVert^4)$$

   Half-angle identity and the cosine series; products of two second-order terms are $O(s^4\Delta_i^2\Delta_j^2)\subseteq O(s^4\lVert\Delta\rVert^4)$. The Gaussian $e^{-\gamma\lVert\Delta\rVert^2}=1-\gamma\lVert\Delta\rVert^2+O(\lVert\Delta\rVert^4)$ matches for $\gamma=s^2/4$: this is (b).
6. 6
   Step 6:

   $$\frac{\mathrm d}{\mathrm d\delta}\cos^2\frac{s\delta}2=-\frac s2\sin(s\delta)<0\quad(0<s\delta<\pi)$$

   For $s\le\pi$ and $\delta=\lvert\Delta_j\rvert\in(0,1]$ we have $0<s\delta\le\pi$, so similarity decreases strictly with distance in each feature: the first part of (c).
7. 7
   Step 7:

   $$s=2\pi,\ \Delta_j=1:\quad\cos^2\pi=1,\qquad R_X(2\pi)\lvert0\rangle=-\lvert0\rangle=-R_X(0)\lvert0\rangle$$

   The rotation by $2\pi$ returns every state up to the global phase $-1$: the two ends of the feature range are identified (aliasing), the second part of (c).
8. 8
   Step 8:

   $$\lvert1-K_s(u,u')\rvert\le\frac{s^2}4\lVert\Delta\rVert^2\le\frac{s^2d}4\ \to\ 0\quad(s\to0)$$

   From $1-\cos^2\frac t2=\sin^2\frac t2\le\frac{t^2}4$ and $1-\prod_ja_j\le\sum_j(1-a_j)$ for $a_j\in[0,1]$ (induction on $d$). With every entry near $1$ the Gram matrix approaches $\mathbf 1\mathbf 1^\top$, the decision function $\sum_i\alpha_iy_iK(x_i,x)+b$ tends to a constant, and the classifier cannot separate anything: (d).