Universal variational quantum computation

Abstract

Variational quantum algorithms dominate contemporary gate-based quantum enhanced optimisation [1], eigenvalue estimation [2] and machine learning [3]. Here we establish the quantum computational universality of variational quantum computation by developing two objective functions which minimise to prepare states with high 2-norm overlap with the outputs of quantum circuits. The fleeting resource is the number of expected values which must be iteratively minimised using a classical-to-quantum feedback loop. An efficient solution to this optimisation problem is given by considering the quantum circuit being simulated itself. The first construction is efficient in the number of expected values for $n$-qubit circuits containing $\mathcal{O}(\text{poly} \ln n)$ non-Clifford gates$-$the number of expected values has no dependence on Clifford gates appearing in the simulated circuit. The second approach adapts the Feynman-Kitaev clock construction yielding $\mathcal{O}(L^2)$ expected values while introducing not more than $\mathcal{O}(\ln L)$ slack qubits, for a quantum circuit partitioned into $L$ Hermitian blocks (gates). The variational model is hence universal and necessitates (i) state-preparation by a control sequence followed by (ii) measurements in one basis. Resources can be reduced by gradient-free or gradient-based minimisation of a polynomially bounded number of expected values. Partitions of the circuit being simulated seed an iterative classical-to-quantum feedback and optimization process which seeks to reduce coherence time.