RSRoberto Sebastiani

Roberto Sebastiani

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Roberto Sebastiani has a total of 38 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Experimenting with D-Wave quantum annealers on prime factorization problems

    by Jingwen Ding, Giuseppe Spallitta, Roberto Sebastiani

    This paper builds on top of a paper we have published very recently, in which we have proposed a novel approach to prime factorization (PF) by quantum annealing, where 8, 219, 999 = 32, 749 × 251 was the highest prime product we were able to factorize—which, to the best of our knowledge is the largest number which was ever factorized by means of a quantum device. The series of annealing experiments which led us to these results, however, did not follow a straight-line path; rather, they involved a convoluted trial-and-error process, full of failed or partially-failed attempts and backtracks, which only in the end drove us to find the successful annealing strategies. In this paper, we delve into the reasoning behind our experimental decisions and provide an account of some of the attempts we have taken before conceiving the final strategies that allowed us to achieve the results. This involves also a bunch of ideas, techniques, and strategies we investigated which, although turned out to be inferior wrt. those we adopted in the end, may instead provide insights to a more-specialized audience of D-Wave users and practitioners. In particular, we show the following insights: (i) different initialization techniques affect performances, among which flux biases are effective when targeting locally-structured embeddings; (ii) chain strengths have a lower impact in locally-structured embeddings compared to problem relying on global embeddings; (iii) there is a trade-off between broken chain and excited CFAs, suggesting an incremental annealing offset remedy approach based on the modules instead of single qubits. Thus, by sharing the details of our experiences, we aim to provide insights into the evolving landscape of quantum annealing, and help people access and effectively use D-Wave quantum annealers.


  • Open Access

    Disjoint Partial Enumeration without Blocking Clauses

    by Giuseppe Spallitta, Roberto Sebastiani, Armin Biere

    A basic algorithm for enumerating disjoint propositional models (disjoint AllSAT) is based on adding blocking clauses incrementally, ruling out previously found models. On the one hand, blocking clauses have the potential to reduce the number of generated models exponentially, as they can handle partial models. On the other hand, the introduction of a large number of blocking clauses affects memory consumption and drastically slows down unit propagation. We propose a new approach that allows for enumerating disjoint partial models with no need for blocking clauses by integrating: Conflict-Driven Clause-Learning (CDCL), Chronological Backtracking (CB), and methods for shrinking models (Implicant Shrinking). Experiments clearly show the benefits of our novel approach.


  • Open Access

    Effective prime factorization via quantum annealing by modular locally-structured embedding

    by Jingwen Ding, Giuseppe Spallitta, Roberto Sebastiani

    This paper investigates novel techniques to solve prime factorization by quantum annealing (QA). First, we present a very-compact modular encoding of a multiplier circuit into the architecture of current D-Wave QA devices. The key contribution is a compact encoding of a controlled full-adder into an 8-qubit module in the Pegasus topology, which we synthesized using Optimization Modulo Theories. This allows us to encode up to a 21 × 12-bit multiplier (and a 22 × 8-bit one) into the Pegasus 5760-qubit topology of current annealers. To the best of our knowledge, these are the largest factorization problems ever encoded into a quantum annealer. Second, we investigated the problem of actually solving encoded PF problems by running an extensive experimental evaluation on a D-Wave Advantage 4.1 quantum annealer. In the experiments we introduced different approaches to initialize the multiplier qubits and adopted several performance enhancement techniques. Overall, 8,219,999 = 32,749 × 251 was the highest prime product we were able to factorize within the limits of our QPU resources. To the best of our knowledge, this is the largest number which was ever factorized by means of a quantum annealer; also, this is the largest number which was ever factorized by means of any quantum device without relying on external search or preprocessing procedures run on classical computers.


  • Open Access

    Disjoint Partial Enumeration without Blocking Clauses

    by Giuseppe Spallitta, Roberto Sebastiani, Armin Biere

    A basic algorithm for enumerating disjoint propositional models (disjoint AllSAT) is based on adding blocking clauses incrementally, ruling out previously found models. On the one hand, blocking clauses have the potential to reduce the number of generated models exponentially, as they can handle partial models. On the other hand, the introduction of a large number of blocking clauses affects memory consumption and drastically slows down unit propagation. We propose a new approach that allows for enumerating disjoint partial models with no need for blocking clauses by integrating: Conflict-Driven Clause-Learning (CDCL), Chronological Backtracking (CB), and methods for shrinking models (Implicant Shrinking). Experiments clearly show the benefits of our novel approach.

  • Open Access

    Effective Prime Factorization via Quantum Annealing by Modular Locally-structured Embedding

    by Jingwen Ding, Giuseppe Spallitta, Roberto Sebastiani

    This paper investigates novel techniques to solve prime factorizationby quantum annealing (QA).First, we present a very-compact modular encoding of amultiplier circuit into the architecture of current D-Wave QA devices.The key contribution is a compact encoding of a controlled full-adderinto an 8-qubit module in the Pegasus topology, which we synthesizedby means of Optimization Modulo Theories. This allows us to encode upto a 21×12-bit multiplier (and a 22×8-bit one) into the Pegasus5760-qubit topology of current annealers. To the best of ourknowledge, these are the largest factorization problems ever encodedinto a quantum annealer.Second, we investigated the problem of actually solving encodedPF problems by running an extensive experimental evaluation on aD-Wave Advantage 4.1 quantum annealer. In the experiments weintroduced different approaches to initialize the multiplier qubitsand adopted several performance enhancement techniques. Overall,8,219,999=32,749×251 was the highest prime product we were able tofactorize within the limits of our QPU resources. To the best of ourknowledge, this is the largest number which was ever factorized bymeans of a quantum device.


  • Open Access

    Effective Prime Factorization via Quantum Annealing by Modular Locally-structured Embedding

    by Jingwen Ding, Giuseppe Spallitta, Roberto Sebastiani

    This paper investigates novel techniques to solve prime factorization by quantum annealing (QA). Our contribution is twofold. First, we present a novel and very compact modular encoding of a binary multiplier circuit into the Pegasus architecture of current D-Wave QA devices. The key contribution is a compact encoding of a controlled full-adder into an 8-qubit module in the Pegasus topology, which we synthesized offline by means of Optimization Modulo Theories. This allows us to encode up to a 21*12-bit multiplier (and a 22*8-bit one) into the Pegasus 5760-qubit topology of current annealers. To the best of our knowledge, these are the largest factorization problems ever encoded into a quantum annealer. Second, we have investigated the problem of actually solving encoded PF problems by running an extensive experimental evaluation on a D-Wave Advantage 4.1 quantum annealer. In order to help the annealer in reaching the global minimum, in the experiments we introduced different approaches to initialize the multiplier qubits and adopted several performance enhancement techniques. Overall, exploiting all the encoding and solving techniques described in this paper, 8, 219, 999 = 32, 749 * 251 was the highest prime product we were able to factorize within the limits of our QPU resources. To the best of our knowledge, this is the largest number which was ever factorized by means of a quantum annealer, and, more generally, by a quantum device.

  • Optimization Modulo Non-linear Arithmetic via Incremental Linearization

    by Filippo Bigarella, Alessandro Cimatti, Alberto Griggio, Ahmed Irfan, Martin Jonáš, Marco Roveri, Roberto Sebastiani, Patrick Trentin


  • Open Access

    Optimization Modulo the Theories of Signed Bit-Vectors and Floating-Point Numbers

    by Patrick Trentin, Roberto Sebastiani

    Optimization modulo theories (OMT) is an important extension of SMT which allows for finding models that optimize given objective functions, typically consisting in linear-arithmetic or Pseudo-Boolean terms. However, many SMT and OMT applications, in particular from SW and HW verification, require handling bit-precise representations of numbers, which in SMT are handled by means of the theory of bit-vectors ( $${{\mathcal {B}}}{{\mathcal {V}}}$$ B V ) for the integers and that of floating-point numbers ( $$\mathcal {FP}$$ FP ) for the reals respectively. Whereas an approach for OMT with (unsigned) $${{\mathcal {B}}}{{\mathcal {V}}}$$ B V objectives has been proposed by Nadel & Ryvchin, unfortunately we are not aware of any existing approach for OMT with $$\mathcal {FP}$$ FP objectives. In this paper we fill this gap, and we address for the first time $$\text {OMT}$$ OMT with $$\mathcal {FP}$$ FP objectives. We present a novel OMT approach, based on the novel concept of attractor and dynamic attractor, which extends the work of Nadel and Ryvchin to work with signed- $${{\mathcal {B}}}{{\mathcal {V}}}$$ B V objectives and, most importantly, with $$\mathcal {FP}$$ FP objectives. We have implemented some novel $$\text {OMT}$$ OMT procedures on top of OptiMathSAT and tested them on modified problems from the SMT-LIB repository. The empirical results support the validity and feasibility of our novel approach.


  • Solving SAT (and MaxSAT) with a quantum annealer: Foundations, encodings, and preliminary results

    by Zhengbing Bian, Fabian Chudak, William Macready, Aidan Roy, Roberto Sebastiani, Stefano Varotti