On the Representation of Boolean and Real Functions as Hamiltonians for Quantum Computing
Author:
Top Cited Papers
Open Access
- 21 December 2021
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Quantum Computing
- Vol. 2 (4) , 1-21
Abstract
Mapping functions on bits to Hamiltonians acting on qubits has many applications in quantum computing. In particular, Hamiltonians representing Boolean functions are required for applications of quantum annealing or the quantum approximate optimization algorithm to combinatorial optimization problems. We show how such functions are naturally represented by Hamiltonians given as sums of Pauli Z operators (Ising spin operators) with the terms of the sum corresponding to the function’s Fourier expansion. For many classes of Boolean functions which are given by a compact description, such as a Boolean formula in conjunctive normal form that gives an instance of the satisfiability problem, it is #P-hard to compute its Hamiltonian representation, i.e., as hard as computing its number of satisfying assignments. On the other hand, no such difficulty exists generally for constructing Hamiltonians representing a real function such as a sum of local Boolean clauses each acting on a fixed number of bits as is common in constraint satisfaction problems. We show composition rules for explicitly constructing Hamiltonians representing a wide variety of Boolean and real functions by combining Hamiltonians representing simpler clauses as building blocks, which are particularly suitable for direct implementation as classical software. We further apply our results to the construction of controlled-unitary operators, and to the special case of operators that compute function values in an ancilla qubit register. Finally, we outline several additional applications and extensions of our results to quantum algorithms for optimization. A goal of this work 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 provide a unified framework for the various constructions appearing in the literature.Keywords
All Related Versions
Funding Information
- USRA Feynman Quantum Computing Academy summer internship program
- NASA Ames Research Center
- NASA Academic Mission Services (NNA16BD14C)
This publication has 34 references indexed in Scilit:
- Nonperturbative-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spinsPhysical Review A, 2008
- Polynomial degree vs. quantum query complexityJournal of Computer and System Sciences, 2006
- Programmable Networks for Quantum AlgorithmsPhysical Review Letters, 2003
- Pseudo-Boolean optimizationDiscrete Applied Mathematics, 2002
- Quantum lower bounds by polynomialsJournal of the ACM, 2001
- Quantum annealing in the transverse Ising modelPhysical Review E, 1998
- On the degree of boolean functions as real polynomialscomputational complexity, 1994
- Constant depth circuits, Fourier transform, and learnabilityJournal of the ACM, 1993
- On the computational complexity of Ising spin glass modelsJournal of Physics A: General Physics, 1982
- The Logic of Quantum MechanicsAnnals of Mathematics, 1936