# Certifiable randomness from a quantum server Why it is important theoretically: 1. It gives a **classical way to certify quantum behavior**. 2. It is a building block for **classical verification of quantum computation**. 3. It connects **quantum computation**, **cryptography**, and **complexity theory** 4. It shows that a quantum computer can provide security services that classical computers cannot easily replicate. ## The method of "A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device" The client is classic and server is quantum. client publish public TCF pair $f_0,f_1$ based on LWE with a trapdoor. more on this below. server generates qubits $\sum_{b\in\{0,1\}, x\in\{0,1\}^n} |b\rangle|x\rangle|0\rangle^n$ and compute $f_b$ [[Unitarian branching on qubits|branching]] on $|b\rangle$ and gets $\sum_{b\in\{0,1\}, x\in\{0,1\}^n} |b\rangle|x\rangle |f_b(x)\rangle$, then it measure the qubits of $|f_b(x)\rangle$ and get a classic value $y$. The qubits collapse to $|\psi\rangle:=\frac{1}{\sqrt 2}(|0\rangle|x_0\rangle+|1\rangle|x_1\rangle)$ s.t., $f_0(x_0)=f_1(x_1)=y$. The server commits to $y$ by sending it to the client. The client uses the trapdoor to compute $x_0,x_1$ from $y$. The client randomly sends the server one of two challenges: preimage-challenge or equation-challenge. Then the cycle repeats with the client generating a new public TCF. - pre-image-challenge: The server measure $|\psi\rangle$ in the computation basis and sends $(b,x_b)$ to the client. The client verifies that $x_b$ is the preimage of $y$ i.e., $f_b(x_b)=y$ and use $b$ as the random bit from this cycle. - equation-challenge: The server measure in the Hadamard basis i.e., it computes $H\otimes H^n|\psi\rangle$ and measure $(a,d)$. Then, send the client $(a,d)$ which computes $d(x_0\oplus x_1)\bmod 2$ and verifies that it equals to $a$. Why $a=d(x_0\oplus x_1)\bmod 2$? $H|b\rangle=\frac{1}{\sqrt 2}\sum_{a\in\{0,1\}}(-1)^{ab}|a\rangle$ and $H^{\otimes n}|x_b\rangle = \frac{1}{\sqrt{2^n}}\sum_{d\in\{0,1\}^n}(-1)^{d\cdot x_b}|d\rangle$ so $ \begin{align} H^{\otimes (n+1)}|\psi\rangle &=\sum_{a\in\{0,1\},d\in\{0,1\}^n}(-1)^{d\cdot x_0}|a,d\rangle+(-1)^a(-1)^{d\cdot x_1}|a,d\rangle \\ &= \sum_{a\in\{0,1\},d\in\{0,1\}^n}((-1)^{d\cdot x_0}+(-1)^{a+d\cdot x_1})|a,d\rangle \end{align} $ The non-zero amplitude require that the exponent will be the same mod 2 i.e., $d\cdot x_0=a+d\cdot x_1\bmod 2$ which is equivalent to $a=d(x_0\oplus x_1)$. LWE is used as for TCF pair: sample $A\in\mathbb{Z}_q^{m\times n},s\in\mathbb{Z}^n,e\leftarrow \chi^m$. let $u=As+e\bmod q$. define $f_0(x)\approx Ax\bmod q$ , $f_1(x)\approx Ax+u\bmod q$. we have $f_1(x)=Ax+As+e=A(x+s)+e=f_0(x+s)\bmod q$. Therefore, $x,x+s$ are claws. Finding the pre-images from $f_0,f_1$ is equivalent to finding $s$ and this is hard on classical computer due to the LWE problem. The trapdoor is a short lattice basis $T_A$ associated with the matrix $A$. Given $A,T_A,y$, the verifier can recover unique short $x$ s.t., $y\approx Ax\bmod q$. uniqueness is achieved by choosing LWE parameters so there is no none-zero short vector in the lattice associated with $A$ with overwhelming probability. Questions: - how many gates and qubits? - Is it practical? - what is the rate of random bit generation - can other function be used that are q-friendly. - how is LWE implemented as quantum gates? how is linear algebra computed in quantum computers. Reference: https://arxiv.org/pdf/1804.00640 ## Created 2026-05-31 12:07