Universal variational quantum computation

Variational quantum algorithms dominate contemporary gate-based quantum enhanced optimization, eigenvalue estimation, and machine learning. Here we establish the quantum computational universality of variational quantum computation by developing two objective functions which minimize to prepare outputs of arbitrary quantum circuits. The fleeting resource of variational quantum computation is the number of expected values which must be iteratively minimized using classical-to-quantum outer loop optimization. An efficient solution to this optimization problem is given by the quantum circuit being simulated itself. The first construction is efficient in the number of expected values for n-qubit circuits containing O(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 yields O(L-2) expected values whereas introducing not more than O(ln L) slack qubits for a quantum circuit partitioned into L gates. Hence, the utilitarian variational quantum programming procedure-based on the classical evaluation of objective functions and iterated feedback-is, in principle, as powerful as any other model of quantum computation. This result elevates the formal standing of the variational approach whereas establishing a universal model of quantum computation.

Automated summary

Variational quantum algorithms are shown to be computationally universal by developing objective functions that minimize the output preparation of arbitrary quantum circuits. The optimization of expected values in variational quantum computation relies on an iterative classical-to-quantum outer loop optimization, with the quantum circuit itself providing an efficient solution. This approach is efficient for n-qubit circuits with non-Clifford gates, and can handle various quantum circuit structures effectively.