Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1401.2248

Boolean Functions, Quantum Gates, Hamilton Operators, Spin Systems and Computer Algebra

Yorick Hardy, Willi-Hans Steeb

Published Jan 10, 2014• 0 citations
arXivHTMLPDF

Abstract

We describe the construction of quantum gates (unitary operators) from boolean functions and give a number of applications. Both non-reversible and reversible boolean functions are considered. The construction of the Hamilton operator for a quantum gate is also described with the Hamilton operator expressed as spin system. Computer algebra implementations are provided.

DOI
10.48550/arxiv.1401.2248

Related papers

On the Representation of Boolean and Real Functions as Hamiltonians for Quantum Computing

Stuart Hadfield

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.

arXiv:1804.09130•ACM Transactions on Quantum Computing•Dec 21, 2021•86 citations

On the Relationship between Boolean Algebra and Quantum Informatics

Yu. I. Bogdanov, Nadezhda A. Bogdanova, Dmitriy V. Fastovets +1 more

Abstract The fundamental relationship between quantum physics and discrete mathematics is examined. A method for representing Boolean functions in the form of unitary transformations is described. The question of the connection of Zhegalkin polynomials defining the algebraic normal form of a Boolean function with quantum circuits is considered. It is shown that the quantum information language provides a simple algorithm for constructing the Zhegalkin polynomial based on the truth table. The developed methods and algorithms are generalized to the case of an arbitrary Boolean function with a multibit domain of definition and a multibit set of values, as well as to the case of multivalued ($$k$$-value) logic when $$k = p$$ is a prime number. The developed approach is important for the implementation of quantum computer technologies and is the foundation for the transition from classical computer logic to quantum hardware.

Russian Microelectronics•Jan 1, 2020•0 citations

Quantum information processing 1: the quantum emulation of familiar invertible digital gates

Helmut Bez, Tony Croft

This chapter aims to define quantum equivalents of a number of familiar digital gates. It argues that the quantum gates, with appropriately restricted state vector inputs, produce exactly the same numerical outputs as their digital counterparts. Hence, although current digital technology is not based on invertible Boolean functions, in order to emulate digital computation quantum mechanically, it is necessary to first construct invertible representations of Boolean functions. The chapter considers only some of the more familiar examples – up to and including the Peres half-adder. In the graphical representation of quantum gates and circuits, the horizontal lines indicate the time-ordered application of the unitary gates to the input qubits.

Chapman & Hall/CRC eBooks•Jan 6, 2023•0 citations

Representation of Boolean functions in terms of quantum computation

Dmitriy V. Fastovets, Yu. I. Bogdanov, Nadezhda A. Bogdanova +1 more

The relationship between quantum physics and discrete mathematics is reviewed in this article. The Boolean functions unitary representation is considered. The relationship between Zhegalkin polynomial, which defines the algebraic normal form of Boolean function, and quantum logic circuits is described. It is shown that quantum information approach provides simple algorithm to construct Zhegalkin polynomial using truth table. Developed methods and algorithms have arbitrary Boolean function generalization with multibit input and multibit output. Such generalization allows us to use many-valued logic (k-valued logic, where k is a prime number). Developed methods and algorithms can significantly improve quantum technology realization. The presented approach is the baseline for transition from classical machine logic to quantum hardware.

arXiv:1906.06374•International Conference on Micro- and Nano-Electronics (ICMNE)•Mar 15, 2019•7 citations

Reversible Computing Foundations in Quantum Computation: From Classical Logic to Quantum Algorithms

Keval Barvaliya

Reversible computing provides a foundational framework for understanding quantum computation.This paper first examines classical reversible logic gates, including the CNOT and Toffoli gates, and demonstrates how they can simulate arbitrary Boolean functions.We then extend these concepts to quantum gates and circuits, where all operations are inherently unitary and reversible.Quantum algorithms such as the Deutsch-Jozsa algorithm, phase estimation, and Shor's factoring algorithm are discussed to illustrate how reversibility enables exponential computational speedups.Finally, current challenges and future directions in quantum hardware and algorithm design are presented.Highlighting the essential role of reversible computing in the realisation of practical quantum computers.

Advances in intelligent systems research/Advances in Intelligent Systems Research•Jan 1, 2026•0 citations

r-Universal reversible logic gates

Alexis De Vos, Leo Storme

Reversible logic plays a fundamental role both in ultra-low power electronics and in quantum computing. It is therefore important to know which reversible logic gates can be used as building block for the reversible implementation of an arbitrary boolean function and which cannot.

Journal of Physics A Mathematical and General•May 19, 2004•6 citations
We describe the construction of quantum gates (unitary operators) from boolean functions and give a number of applications. Both non-reversible and reversible boolean functions are considered. The construction of the Hamilton operator for a quantum gate is also described with the Hamilton operator expressed as spin system. Computer algebra implementations are provided.
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.
Abstract The fundamental relationship between quantum physics and discrete mathematics is examined. A method for representing Boolean functions in the form of unitary transformations is described. The question of the connection of Zhegalkin polynomials defining the algebraic normal form of a Boolean function with quantum circuits is considered. It is shown that the quantum information language provides a simple algorithm for constructing the Zhegalkin polynomial based on the truth table. The developed methods and algorithms are generalized to the case of an arbitrary Boolean function with a multibit domain of definition and a multibit set of values, as well as to the case of multivalued (kkk-value) logic when k=pk = pk=p is a prime number. The developed approach is important for the implementation of quantum computer technologies and is the foundation for the transition from classical computer logic to quantum hardware.
This chapter aims to define quantum equivalents of a number of familiar digital gates. It argues that the quantum gates, with appropriately restricted state vector inputs, produce exactly the same numerical outputs as their digital counterparts. Hence, although current digital technology is not based on invertible Boolean functions, in order to emulate digital computation quantum mechanically, it is necessary to first construct invertible representations of Boolean functions. The chapter considers only some of the more familiar examples – up to and including the Peres half-adder. In the graphical representation of quantum gates and circuits, the horizontal lines indicate the time-ordered application of the unitary gates to the input qubits.
The relationship between quantum physics and discrete mathematics is reviewed in this article. The Boolean functions unitary representation is considered. The relationship between Zhegalkin polynomial, which defines the algebraic normal form of Boolean function, and quantum logic circuits is described. It is shown that quantum information approach provides simple algorithm to construct Zhegalkin polynomial using truth table. Developed methods and algorithms have arbitrary Boolean function generalization with multibit input and multibit output. Such generalization allows us to use many-valued logic (k-valued logic, where k is a prime number). Developed methods and algorithms can significantly improve quantum technology realization. The presented approach is the baseline for transition from classical machine logic to quantum hardware.
Reversible computing provides a foundational framework for understanding quantum computation.This paper first examines classical reversible logic gates, including the CNOT and Toffoli gates, and demonstrates how they can simulate arbitrary Boolean functions.We then extend these concepts to quantum gates and circuits, where all operations are inherently unitary and reversible.Quantum algorithms such as the Deutsch-Jozsa algorithm, phase estimation, and Shor's factoring algorithm are discussed to illustrate how reversibility enables exponential computational speedups.Finally, current challenges and future directions in quantum hardware and algorithm design are presented.Highlighting the essential role of reversible computing in the realisation of practical quantum computers.