Mapping functions to Hamiltonians for Quantum Computing

What is it about?

Mapping functions on bits to Hamiltonians acting on qubits has many applications in quantum computing, in particular quantum approaches to hard problems in combinatorial optimization. We show how such functions are naturally represented by Hamiltonians given as sums of Ising spin operators (Pauli Z operators) with the terms of the sum uniquely determined from Fourier analysis. Using this theory we derive rules for methodically mapping common representations such as Boolean clauses or formulas to Hamiltonians, and for combining simple primitives to map arbitrarily complex functions, including real-values ones. We also address computational complexity considerations as to when such Hamiltonians can or cannot be derived and expressed efficiently. Finally, we outline several additional applications and extensions of our results such as the construction of controlled quantum gates, which includes the special case of quantum gates that compute function values as data stored in an ancilla qubit register.

Featured Image

Photo by Joan Gamell on Unsplash

Photo by Joan Gamell on Unsplash

Why is it important?

Our results apply to a wide variety of well-known quantum algorithms. Indeed, a primary goal of this paper is to provide a design toolkit for quantum optimization which may be utilized by experts and practitioners alike in the construction and analysis of new quantum algorithms, and at the same time to demystify the various constructions appearing in the literature.