Source-linked AI summary
On the representation of Boolean and real functions as Hamiltonians for quantum computing
Stuart Hadfield
TL;DR
Quantum algorithms for decision and optimization problems use Hamiltonians representing functions on bit strings, but constructing these representations can be difficult for general Boolean functions. The paper gives Fourier-based representations and composition rules, then applies them to real-valued objectives and controlled operations. It shows that CNF-SAT representations can entail #P-hard coefficient computation, while providing constructions for weighted sums of local clauses.
Problem
Quantum optimization and related algorithms require mappings from bit-string functions to qubit Hamiltonians, while prior constructions have often focused on quadratic reductions that use additional qubits.
Source: §1 · p. 2Method
The paper represents functions by diagonal Hamiltonians with Pauli Z terms from Fourier expansions and gives composition rules for constructing representations from simpler functions.
Source: §1 · p. 2Results
Computing the identity coefficient for a CNF-SAT Hamiltonian is #P-hard, while weighted sums of local Boolean clauses admit Hamiltonian constructions.
Source: §1 · pp. 2–3Takeaways & Limitations
The results provide a unified design toolkit for optimization mappings and extend to controlled unitaries and reversible computation in an ancilla register.
Source: §5 · pp. 16–17General Boolean functions may have exponentially many Pauli terms, and computing their Hamiltonian representations can be computationally intractable.
Source: §2.1 · p. 9
Abstract
from arXiv · showhide
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 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. On the other hand, no such difficulty exists generally for constructing Hamiltonians representing a real function such as a sum of local Boolean clauses. We give composition rules for explicitly constructing Hamiltonians representing a wide variety of Boolean and real functions by combining Hamiltonians representing simpler clauses as building blocks. We 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. A primary goal of this paper is to provide a $\textit{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.
1 Introduction
The paper develops a toolkit for representing Boolean and real functions as diagonal qubit Hamiltonians and composing representations of simpler functions. It also identifies computational limits for general Boolean functions and applies the constructions to controlled operations and reversible function computation.
1 Introduction
- The toolkit targets quantum optimization and related algorithms, while aiming to make Hamiltonian and circuit mappings accessible for researchers across domains.The authors describe the results as supporting straightforward software generation of mappings.Source: §1 · pp. 1–2
1.1.1 Boolean Functions
- A Boolean function has a unique diagonal Hamiltonian whose Pauli Z terms correspond to its Fourier expansion.The representation applies to functions on n bits, including functions depending on fewer than n bits.Source: §1.1.1 · pp. 3–4
- For CNF satisfiability, computing the identity coefficient of the Hamiltonian is #P-hard; general Boolean representations may also require exponentially many Pauli terms.The identity coefficient is the first Fourier coefficient, and computing the representation is at least as hard as computing it.Source: §1.1.1 · p. 4
1.1.2 Constructing Hamiltonians using Propositional Logic
- Negation, conjunction, disjunction, exclusive-or, implication, and real scaling or addition have composition rules for combining Boolean-function Hamiltonians.These rules support constructing representations for more complex formulas and circuits from basic clauses.Source: §1.1.2 · pp. 4–5
1.1.3 Pseudo-Boolean functions
- A real-valued function on n bits also has a unique diagonal Hamiltonian, extending the Boolean-function representation to pseudo-Boolean objectives.Such objectives include weighted sums of Boolean clauses used in constraint-satisfaction settings.Source: §1.1.3 · p. 5
1.1.4 Controlled Hamiltonians and Unitaries
- The constructions extend to Boolean-controlled evolution under an arbitrary Hamiltonian, including controls beyond AND functions.For QAOA, these controls can restrict mixing evolution to feasible states.Source: §1.1.4 · p. 6
1.1.5 Computing Boolean Functions in a Register
- The paper applies the representations to reversible computation of Boolean values in an ancilla register, with corresponding Hamiltonians and unitary operators.For SAT, computing the identity coefficient of the resulting operator is #P-hard.Source: §1.1.5 · pp. 6–7
2 Representing n-bit Functions as Diagonal Qubit Hamiltonians
Boolean and real functions on n bits have natural diagonal Hamiltonian representations built from Pauli Z terms and Fourier coefficients. The section gives rules for composing these representations, establishes construction bounds for sums of local clauses, and identifies counting-related hardness for general Boolean functions.
2.1 Boolean Functions
- Each Boolean function has a unique diagonal Hamiltonian representation, with Pauli Z products corresponding to its Fourier expansion.The representation acts as the function’s multiplication operator on computational-basis states.Source: §2 · p. 7, §2.1 · pp. 7–8
- Computing a Boolean function’s Hamiltonian representation can be as hard as counting its satisfying inputs, and arbitrary representations may have exponential size.The identity coefficient can be #P-hard to compute; exponential size also prevents efficient direct simulation.Source: §2.1 · p. 9
2.2 Basic Clauses and Logical Composition Rules
- Composition rules construct Hamiltonians for arbitrary Boolean formulas and circuits from representations of simpler functions.The rules translate complement, conjunction, disjunction, and related logical operations into Hamiltonian combinations.Source: §2.1 · p. 9, §2.2 · p. 10
2.3 Pseudo-Boolean Functions and Constraint Satisfaction Problems
- Hamiltonians for real functions are weighted sums of the Hamiltonians for their Boolean components.The Fourier expansion is linear, and the resulting real-function Hamiltonian is unique.Source: §2.3 · pp. 10–11
- For f = sum_j w_j f_j, the Hamiltonian degree is at most max_j deg(f_j), and its size is at most min{sum_j size(H_fj), (e/d)^d n^d + 1}.The bounds apply to weighted sums of Boolean clauses.Source: §2.3 · p. 11
- For a conjunction of clauses, the sum of squared Fourier coefficients equals E[f] exactly when the clauses are pairwise orthogonal.The passage also states that if some pair of clauses has zero inner product, their conjunction is unsatisfiable.Source: §2.3 · p. 11
3 Applications to Constructing Diagonal Operators
The section applies function Hamiltonians to constrained optimization, ground-state encodings, diagonal evolution, and quadratic binary objectives. It describes penalty terms for enforcing feasibility, a general ground-state construction, ancilla-free simulation bounds, and a quadratic Pauli Z form for QUBO.
3.1 Constrained Optimization
- For constrained optimization, positive-weight penalty terms shift infeasible states so the ground states encode optimal feasible solutions.The weights can be selected to shift infeasible-state eigenvalues away from those of the objective function.Source: §3.1 · pp. 11–12
3.2 Ground State Boolean Logic
- A function’s input-output pairs can be encoded as a Hamiltonian ground-state subspace using a constraint that vanishes exactly when the output equals the function value.The construction applies generally, although simpler Hamiltonians may exist for particular function classes.Source: §3.2 · p. 12
3.3 Simulating Diagonal Hamiltonians
- A Boolean or real function Hamiltonian can be simulated with O(deg(H_f) · size(H_f)) basic gates on n qubits, without ancillas.The passage also states O(nd) gates when the maximum degree d is O(1); the circuit in Figure 1 uses 2(ℓ−1) CNOT gates and one RZ gate for an ℓ-body Z term.Source: Figure 1 · p. 12, §3.3 · p. 13
3.4 Quadratic Unconstrained Binary Optimization
- A QUBO objective maps to a quadratic sum of Pauli Z operators with size(H_f) ≤ 1 + n/2 + n^2/2.The section also derives that the stated Ising decision problem is NP-complete by mapping MAX-2-SAT to a degree-two Hamiltonian.Source: §3.4 · pp. 13–14
4 Applications to non-diagonal operators
The section extends function-Hamiltonian methods to controlled unitaries and operators that compute Boolean values in registers. It relates Boolean controls to conjunctions of Hamiltonians, gives a representation induced by bit-query operators, and connects the resulting oracles to phase queries.
4.1 Controlled Unitaries and Hamiltonians
- A Boolean control combined with a Boolean-function Hamiltonian represents their conjunction, while overlapping-qubit products are not guaranteed to remain self-adjoint.The section also connects the representation of fermionic creation and annihilation operators to the Jordan-Wigner transform.Source: §4.1 · p. 15
4.2 Computing Functions in Registers
- A bit-query operator induces a diagonal Hamiltonian representation of the function, and its identity coefficient gives one minus the fraction of satisfying inputs.The section also states that the bit-query and controlled phase-query oracles are computationally equivalent and both at least as powerful as the phase oracle.Source: §4.2 · p. 16
5 Discussion and Future Work
The discussion presents the results as a toolkit for constructing Hamiltonians and quantum circuits across optimization and related applications. It identifies several possible extensions, while leaving detailed analysis of general Hamiltonians on qubits or qudits for future work.
5 Discussion and Future Work
- The toolkit covers Boolean and pseudo-Boolean optimization mappings, diagonal simulation, constraint penalties or mixers, and controlled unitaries that compute Boolean functions in ancilla registers.The authors describe it as a unified view of existing mappings, including.Source: §5 · pp. 16–17
- Detailed analysis of general Hamiltonians on qubits or qudits remains future work.Other outlined directions include unfaithful representations, statistical mechanics, quantum complexity, and links to classical open problems.Source: §5 · p. 17