## Quantum Kolmogorov Complexity --- ### What is 'Complexity' `01010101010101010101010101010101` vs `11010010111010110001101110010110` -v- We need a way to measure the "innate randomness" or "information content" of an individual object --- ### Classical Kolmogorov Complexity $C_{U}(x) = \displaystyle\min_{p} \set{\vert p \vert : U(p) = x}$ where $U$ is a universal Turing machine --- ### The invariance theorem The choice of the universal machine only affects $C(x)$ by a constant additive factor -v- - Let $U$ and $V$ be universal Turing machines - Let $p_{V}$ be the program for $U$ that simulates $V$ - $U(p_{V}, q)=V(q) \space \forall q$ - Let $q$ be the shortest program that makes $V$ output $x$ - $p_{V} q$ makes $U$ output $x$ - $ C_{U} (x) \le \vert p_{V} \vert + C_{V} (x) $ - Symmetrically, $C_{V} (x) \le \vert p_{U} \vert + C_{U} (x)$ $ \vert C_{U} (x) - C_{V} (x) \vert \le \max(\vert p_{U} \vert ,\vert p_{V} \vert) $ --- ### Some important properties - $\forall x \space \space C(x) \le \vert x \vert + c$ - $\forall n \space \exists x$ of length $n$ such that $C(x) \ge n$ -v- - There are $2^{n}$ binary strings of length $n$ - There exist $2^{n}-1$ distinct programs of length $\lt n$ - Each of these programs can produce at most one output - Thus, not all strings of length $n$ are compressible --- In general, $C(x)$ is not a computable function --- ### Considerations for the quantum case - What model of computation? (New ideas here) - How many times should one generate the output state? (no-cloning) - Produce a state exactly, or upto some fidelity. How is this fidelity parametrized? -v- - Model of computation: Quantum Turing Machines with two heads and one-way tapes - Reusability not required, generating once is enough - What about fidelity? --- Quantum Kolmogorov Complexity with fidelity $f$ $ QC_{M}^{f}(X) = \displaystyle\min_{p} \set{ \vert p \vert : F(X, M(p, 1^{k}) \ge f(k)} $ for some fidelity function $f : \mathbb{N} \rightarrow [0, 1] $ -v- Quantum Kolmogorov Complexity with perfect fidelity : $ QC_{M}^{1} (X) $ Problem: Invariance proof! We deal with _approximating_ procedures -v- Quantum Kolmogorov Complexity with bounded fidelity : $ QC_{M}^{\epsilon} (X) $ for any constant $\epsilon \lt 1$ Problem: Some strings may be very easy to describe up to a given constant, but very hard to describe for a smaller error. Not robust! -v- Quantum Kolmogorov Complexity with fidelity converging to $1$ $ QC_{M}^{\uparrow 1} (X) = QC_{M}^{f} (X) $ where $f(k) = 1-\frac{1}{k}$ --- ### Quantum Kolmogorov Complexity $ QC(X) = \displaystyle\min_{p} \set{ \vert p \vert : F(X, M(p, 1^{k}) \ge 1-\frac{1}{k}} $ -v- - Invariance holds for this! - Intuitively makes sense, formal proof to be fully understood in the second half of the project! --- ### Is it consistent? For any finite, classical string $x$ $ QC(x) \le C(x) + O(1) $ Proof is trivial: a universal quantum Turing machine can simulate a universal Turing machine -v- Interestingly, converse is also true! $ C(x) \le QC(x) + O(1) $ --- ## Turing Machines! --- ### Classical Turing Machine 7 Tuple $ \langle Q, \Gamma, \Sigma, \sqcup, q_{0}, F, \delta \rangle $ - $Q$: finite state set - $\Gamma$: finite tape alphabet - $\Sigma \subset \Gamma$: finite input alphabet - $\sqcup \in \Gamma$: blank symbol, with $ \sqcup \notin \Sigma $ - $q_{0} \in Q$: start state - $F \subseteq Q$: set of end states - $\delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \set{L, R, N} $ -v- ### A nicer formalism - Represent $\delta$ as a transition matrix in the space of configurations - A configuration includes the current local state of the machine, the tape contents and the position of the head - $ c = (q, B, i) \in Q \times \Gamma^{*} \times \mathbb{Z} $ - Replace $\delta$ with a transition matrix $U$ such that - $U_{ji} = 1 $ if $c_i \xrightarrow{\delta} c_j $ - $U_{ji} = 0 $ otherwise -v- So we get our 7 tuple $ \langle Q, \Gamma, \Sigma, \sqcup, q_{0}, F, U \rangle $ Instead of $U_{i j} \in \set{0, 1}$, if we have: - $U_{i j} \in \mathbb{R}$: we get a probabilistic Turing machine - $U_{i j} \in \mathbb{C}$ and $U$ is unitary: we get a **quantum Turing machine** --- ### A critique of the Turing machine model - Unintuitive for _designing_ algorithms - Algorithms aren't expressed at the level of tape heads, alphabets, etc -v- ### The Mapcode formalism - A Turing complete model that describes computation in an intuitive way - An algorithm is a 6 tuple $\langle X, S, T, F, \rho, \pi \rangle$ - $X$, The state space - $S, T$, input and output spaces - $F : X \rightarrow X$, the program map - $\rho : S \rightarrow X$, the input map - $\pi : X \rightarrow T$, the output map -v- ### What do we get from Mapcode? - A formal definition of a computation - Arbitrary levels of abstraction - Program verification and correctness proofs - Termination proofs --- ### Some ideas - Quantum Mapcode Formalism: $\langle \mathcal{H}_{X}, S, T, U_F, \rho, \set{M_k} \rangle$ --- ## In the second half - Kolmogorov Quantity is related to Entropy, read up on that - More examples of quantum algorithms in the quantum mapcode formalism - Attempt to prove equivalence between quantum mapcode formalism and universal quantum Turing machine