Publications associées à Boolean differential calculus

Scalable Logic Rewriting Using Don’t Cares

Giovanni De Micheli, Alessandro Tempia Calvino

Logic rewriting is a powerful optimization technique that replaces small sections of a Boolean network with better implementations. Typically, exact synthesis is used to compute optimum replacement on-the-fly, with possible support for Boolean don't cares. ...

2024

In Medio Stat Virtus: Combining Boolean and Pattern Matching

Giovanni De Micheli, Alessandro Tempia Calvino, Gianluca Radi

Technology mapping transforms a technology-independent representation into a technology-dependent one given a library of cells. This process is performed by means of local replacements that are extracted by matching sections of the subject graph to library ...

IEEE2024

Improving Standard-Cell Design Flow using Factored Form Optimization

Giovanni De Micheli, Alessandro Tempia Calvino

Factored form is a powerful multi-level representation of a Boolean function that readily translates into an implementation of the function in CMOS technology. In particular, the number of literals in a factored form correlates strongly with the number of ...

IEEE2023

A Majority Lemma for Randomised Query Complexity

Mika Tapani Göös, Gilbert Théodore Maystre

We show that computing the majority of n copies of a boolean function g has randomised query complexity R(Maj∘gⁿ) = Θ(n⋅R ̅_{1/n}(g)). In fact, we show that to obtain a similar result for any composed function f∘gⁿ, it suffices to prove a sufficiently stro ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2021

Logic Resynthesis of Majority-Based Circuits by Top-Down Decomposition

Giovanni De Micheli, Heinz Riener, Siang-Yun Lee

Logic resynthesis is the problem of finding a dependency function to re-express a given Boolean function in terms of a given set of divisor functions. In this paper, we study logic resynthesis of majority-based circuits, which is motivated by the increasin ...

IEEE2021

Learning from survey propagation: a neural network for MAX-E-3-SAT

Raffaele Marino

Many natural optimization problems are NP-hard, which implies that they are probably hard to solve exactly in the worst-case. However, it suffices to get reasonably good solutions for all (or even most) instances in practice. This paper presents a new algo ...

IOP PUBLISHING LTD2021

From Boolean functions to quantum circuits: A scalable quantum compilation flow in C++

Giovanni De Micheli, Fereshte Mozafari Ghoraba, Heinz Riener, Giulia Meuli, Bruno Schmitt Antunes

We propose a flow for automated quantum compila- tion. Our flow takes a Boolean function implemented in Python as input and translates it into a format appropriate for reversible logic synthesis. We focus on two quantum compilation tasks: uniform state pre ...

2021

Enumerating Optimal Quantum Circuits using Spectral Classification

Giovanni De Micheli, Mathias Soeken, Giulia Meuli

This work targets fault-tolerant quantum computing and focuses on the problem of mapping reversible circuits into the Clifford+T quantum gate library. We present an automatically-generated database containing minimal-cost quantum circuits for Boolean funct ...

IEEE2020

Advanced Functional Decomposition Using Majority and Its Applications

Giovanni De Micheli, Mathias Soeken, Zhufei Chu

Typical operators for the decomposition of Boolean functions in state-of-the-art algorithms are AND, exclusive-OR (XOR), and the 2-to-1 multiplexer (MUX). We propose a logic decomposition algorithm that uses the majority-of-three (MAJ) operation. Such a de ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2020

Automatic Uniform Quantum State Preparation Using Decision Diagrams

Giovanni De Micheli, Mathias Soeken, Fereshte Mozafari Ghoraba, Heinz Riener

Most quantum algorithms assume some specific initial state in superposition of basis states before performing the desired application-specific computations. The preparation of such states itself requires a computation performed by a quantum circuit. In thi ...

IEEE COMPUTER SOC2020