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

Texts in computer science

Implementation of Boolean Functions

Sergei Kurgalin, Sergei Borzunov

Published Jan 1, 2021• 2 citations
Publisher
DOI
10.1007/978-3-030-65052-0_7

Related papers

Fanout Complexity of Symmetric Boolean Functions in $\mathsf{QAC}^0$

Boyan Xu, Lvzhou Li

Whether $\mathsf{QAC}^0$ can compute $\mathtt{PARITY}_n$ remains open. Computing $\mathtt{PARITY}_n$ is equivalent to implementing $\mathtt{FANOUT}_n$ under $\mathsf{QAC}^0$ reductions. This raises a more general question: for an arbitrary symmetric Boolean function $f:\{0,1\}^n\to\{0,1\}$, what fanout size is necessary and sufficient for computing $f$ in $\mathsf{QAC}^0$? We show that the answer is exactly the transition radius $ρ(f)$: computing $f$ and implementing $\mathtt{FANOUT}_{ρ(f)}$ are equivalent under $\mathsf{QAC}^0$ reductions. In particular, if $ρ(f)\ge n^δ$ for some constant $δ>0$, then computing $f$ is $\mathsf{QAC}^0_{\mathrm{f}}$-complete. Combined with Paturi's theorem, our characterization implies that if $\mathtt{PARITY}_n \notin \mathsf{QAC}^0$, then any Boolean function in $\mathsf{QAC}^0$ of approximate degree $n^{1/2+Ω(1)}$ must be nonsymmetric.

quant-pharXiv:2609.05153•Sep 7, 2026•1 citation

Local Correction of Boolean Functions

Noga Alon, Amit Weinstein

arXiv:1109.3639•Sep 16, 2011•0 citations

Efficient Representation of Boolean Components

Alwin Zulehner, Robert Wille

Springer eBooks•Jan 1, 2020•0 citations

A Modified Adiabatic Quantum Algorithm for Evaluation of Boolean Functions

Jie Sun, Songfeng Lu, Fang Liu

In this paper, we propose a modified construction of the quantum adiabatic algorithm for Boolean functions studied by M. Andrecut et al. [13, 14]. Our algorithm has the time complexity [Formula: see text] for the evaluation of Boolean functions, without additional computational cost of implementing the driving Hamiltonian, which is required by the adiabatic evolution described in [13, 14].

Open Systems & Information Dynamics•Sep 1, 2015•2 citations

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

Yorick Hardy, Willi-Hans Steeb

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.

arXiv:1401.2248•Jan 10, 2014•0 citations

Algorithms and Computation

Masanori Ohya, Igor Vasil'evich Volovich

Theoretical and mathematical physics•Jan 1, 2011•0 citations
Fanout Complexity of Symmetric Boolean Functions in QAC0\mathsf{QAC}^0QAC0
Whether QAC0\mathsf{QAC}^0QAC0 can compute PARITYn\mathtt{PARITY}_nPARITYn​ remains open. Computing PARITYn\mathtt{PARITY}_nPARITYn​ is equivalent to implementing FANOUTn\mathtt{FANOUT}_nFANOUTn​ under QAC0\mathsf{QAC}^0QAC0 reductions. This raises a more general question: for an arbitrary symmetric Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1}, what fanout size is necessary and sufficient for computing fff in QAC0\mathsf{QAC}^0QAC0? We show that the answer is exactly the transition radius ρ(f)ρ(f)ρ(f): computing fff and implementing FANOUTρ(f)\mathtt{FANOUT}_{ρ(f)}FANOUTρ(f)​ are equivalent under QAC0\mathsf{QAC}^0QAC0 reductions. In particular, if ρ(f)≥nδρ(f)\ge n^δρ(f)≥nδ for some constant δ>0δ>0δ>0, then computing fff is QACf0\mathsf{QAC}^0_{\mathrm{f}}QACf0​-complete. Combined with Paturi's theorem, our characterization implies that if PARITYn∉QAC0\mathtt{PARITY}_n \notin \mathsf{QAC}^0PARITYn​∈/QAC0, then any Boolean function in QAC0\mathsf{QAC}^0QAC0 of approximate degree n1/2+Ω(1)n^{1/2+Ω(1)}n1/2+Ω(1) must be nonsymmetric.