### Quantum Kolmogorov Complexity and Quantum Mapcode --- ### Quick Recap - Classical Kolmogorov Complexity - Quantum Kolmogorov Complexity - Turing Machines - Mapcode Formalism -v- ### Classical Kolmogorov Complexity - $C_{U}(x) = \displaystyle\min_{p} \set{\vert p \vert : U(p) = x}$ - The choice of the universal machine only affects $C(x)$ by a constant additive factor - In general, $C(x)$ is not a computable function -v- ### Quantum Kolmogorov Complexity $ QC(X) = \displaystyle\min_{p} \set{ \vert p \vert : F(X, M(p, 1^{k}) \ge 1-\frac{1}{k}} $ - Invariance holds for this - Consistent with the classical definition -v- ### Turing Machines 7 tuple $ \langle Q, \Gamma, \Sigma, \sqcup, q_{0}, F, U \rangle $ - $U_{i j} \in \set{0, 1}$: classical Turing machine - $U_{i j} \in \mathbb{R}$: probabilistic Turing machine - $U_{i j} \in \mathbb{C}$, $U$ is unitary: **quantum Turing machine** -v- ### Mapcode Formalism - A Turing complete model that describes computation in an intuitive way - An algorithm is a 6 tuple $\langle X, I, A, F, \rho, \pi \rangle$ - $X$, The state space - $I, A$, input and answer spaces - $F : X \rightarrow X$, the program map - $\rho : I \rightarrow X$, the input map - $\pi : X \rightarrow A$, the output map --- ### Quantum Mapcode Formalism $M = (I, A, X, \rho, F, T, \Pi)$ - Input Set (I): A set of classical data representing all valid problem instances. - Output Alphabet (A): A set of classical data representing all possible solutions. -v- $M = (I, A, X, \rho, F, T, \Pi)$ - State Space (X): The set of all possible states of the machine, defined as $X \coloneqq \mathcal{D}(\mathcal{H}) \times C$ - $\mathcal{D}(\mathcal{H})$: The quantum store, the set of density matrices on a Hilbert space $\mathcal{H}$. - $C$: The classical store, a set of classical variables (e.g., counters, flags). -v- $M = (I, A, X, \rho, F, T, \Pi)$ - State Preparation Map ($\rho_Q$): A function $\rho_Q: I \to X$ that maps a classical input to an initial hybrid state. -v- $M = (I, A, X, \rho, F, T, \Pi)$ - Evolution Map ($F_Q$): The transition function on the states, $F: X \to X$ $$F(\rho, c) \coloneqq (U_c \rho U_c^\dagger, g(c))$$ where $U_c$ is a unitary operator on $\mathcal{H}$ chosen based on the classical state $c$, and $g: C \to C$ is a classical function that updates the classical store. -v- $M = (I, A, X, \rho, F, T, \Pi)$ - Termination Predicate (T): A predicate $T: X \to \set{\text{true, false}}$ on the hybrid state. The computation halts when $T$ evaluates to true. -v- $M = (I, A, X, \rho, F, T, \Pi)$ - Measurement Operator ($\Pi$): A function that defines the final measurement on the quantum store and the classical logic to interpret the outcome. $\Pi: X \to A$. --- #### An example: Grover's Algorithm - Find marked item $w$ in space $N=2^n$. - We have access to oracle $U_w$ that marks the target state. - State Space ($X = \mathcal{D}(\mathcal{H}) \times C$): - $\mathcal{H}$: $n$-qubit Hilbert space. - $C$: pair of integers $(k, k_{\max})$ representing current and total iterations. -v- - $\rho(N): (|s\rangle\langle s|, (0, \lfloor \frac{\pi}{4}\sqrt{N} \rfloor)$ where $|s\rangle = H^{\otimes n}|0\rangle^{\otimes n}$ - $F_Q(\rho, (k, k_{\max})) \coloneqq (G \rho G^\dagger, (k+1, k_{\max}))$ where $G = (2|s\rangle\langle s| - I)U_w$. - $T(\rho, (k, k_{\max})) \coloneqq k \ge k_{\max}$ - $\Pi$: Measure the register in the computational basis to get $w$. --- - Shor's algorithm can also be written in this formalism relatively easily. - Complete specification in report. --- ### Is this model powerful enough? - Can we specify arbitrary quantum computations in this formalism? - If this can simulate a quantum turing machine, then we are done! -v- - **Claim**: Quantum mapcode $(I, A, X, \rho, F, T, \Pi)$ can simulate a quantum turing machine $ \langle Q, \Gamma, \Sigma, \sqcup, q_{0}, F, U \rangle $ - $I = \Sigma^*, A = \Gamma^*, X = \mathcal{D}(\mathcal{H}) \times \set{\bot}$ where $\mathcal{H}$ is spanned by $|n\rangle |q\rangle |\tau\rangle$ - $n \in \mathbb{Z}$ (head position) - $q \in Q$ (internal state) - $\tau \in \Gamma^{\infty}$ (tape configuration) -v- - **Claim**: Quantum mapcode $(I, A, X, \rho, F, T, \Pi)$ can simulate a quantum turing machine $ \langle Q, \Gamma, \Sigma, \sqcup, q_{0}, F, U \rangle $ - $\rho(x) = |\psi_0\rangle \langle\psi_0|$, $|\psi_0\rangle=|0\rangle_{pos} \otimes |q_0\rangle_{state} \otimes |x\rangle_{tape}$ - $F(\rho, \bot) = (U \rho U^{\dagger}, \bot )$ -v- - **Claim**: Quantum mapcode $(I, A, X, \rho, F, T, \Pi)$ can simulate a quantum turing machine $ \langle Q, \Gamma, \Sigma, \sqcup, q_{0}, F, U \rangle $ - $P_{halt} = I_{pos} \otimes (\sum_{q \in F} |q\rangle \langle q|) \otimes I_{tape}$ - $T(\rho, \bot) = Tr(P_{halt} \rho) == 1$ - $\Pi(\rho, \bot) = Measure(Tr_{pos, state}(\rho))$ -v- - **Claim**: Quantum mapcode $(I, A, X, \rho, F, T, \Pi)$ can simulate a quantum turing machine $ \langle Q, \Gamma, \Sigma, \sqcup, q_{0}, F, U \rangle $ - It is trivial to now show that this mapcode machine perfectly simulates the quantum turing machine. --- ### Yes, it is powerful enough - Also, a quantum turing machine can simulate a quantum mapcode machine. - Explicit construction in report, not interesting. - Quantum Turing Machines and Quantum Mapcode Machines are **equivalent** --- ### Is it useful? - Probably, could be useful for: - Specifying hybrid algorithms - Formal Verification - Compiler IR --- ### Back to information theory - To define Quantum Kolmogorov Complexity with this, we need the notion of a universal quantum mapcode machine. - Similar to how a universal quantum turing machine is defined: - Takes in a description of a quantum mapcode machine and its input - Simulates the input mapcode machine - Check termination and measure --- #### Quantum Kolmogorov Complexity $$QC_{\mathcal{U}}(\rho) = \displaystyle\min_{(|p_g|, |p_u|)} \set{(|p_g|, |p_u|) : F(\mathcal{U}_{QMF}(p_g, p_u, \ldots, 1^k), \rho) \ge 1 - \frac{1}{k} }$$ - By the same simulation argument, this definition is equivalent to the one with the universal turing machine (upto an additive constant) --- #### Interesting Observations - We get a pair for complexity, not just a number! - The pair neatly separates complexity due to - Classical control $g$ - Quantum unitary $U$ - A middle ground between circuit complexity (time) and kolmogorov complexity (space)? --- ### Conclusion - Seems useful