Roberto Sebastiani
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Roberto Sebastiani has a total of 38 co-authors. Here are the top co-authors by number of shared publications:
Giuseppe Spallitta
3 shared publications- Giuseppe Spallitta
DISI University of Trento
3 shared publications Jingwen Ding
3 shared publications- Alessandro Cimatti
Fondazione Bruno Kessler
2 shared publications - Armin Biere
University of Freiburg
2 shared publications - Chi Mai Nguyen
Viettel High Technology Industries Corporation, Viettel Group Ha Noi
2 shared publications
Latest Publications
- Open Access
- 12 June 2024
- Published by Frontiers Media SA in Frontiers in Computer Science
- Vol. 6, 1335369
Experimenting with D-Wave quantum annealers on prime factorization problems
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.
- 12 June 2024
- Published by Frontiers Media SA in Frontiers in Computer Science
- Vol. 6, 1335369
Open AccessExperimenting with D-Wave quantum annealers on prime factorization problems
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
- 24 March 2024
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 38 (8) , 8126-8135
Disjoint Partial Enumeration without Blocking Clauses
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.
- 24 March 2024
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 38 (8) , 8126-8135
Open AccessDisjoint Partial Enumeration without Blocking Clauses
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
- 12 February 2024
- Published by Springer Nature in Scientific Reports
- Vol. 14 (1) , 1-14
Effective prime factorization via quantum annealing by modular locally-structured embedding
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.
- 12 February 2024
- Published by Springer Nature in Scientific Reports
- Vol. 14 (1) , 1-14
Open AccessEffective prime factorization via quantum annealing by modular locally-structured embedding
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
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 AccessDisjoint Partial Enumeration without Blocking Clauses
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
- 1 November 2023
- Published by Springer Nature in Research Square
Effective Prime Factorization via Quantum Annealing by Modular Locally-structured Embedding
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.
- 1 November 2023
- Published by Springer Nature in Research Square
Open AccessEffective Prime Factorization via Quantum Annealing by Modular Locally-structured Embedding
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
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.
Open AccessEffective Prime Factorization via Quantum Annealing by Modular Locally-structured Embedding
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.
- 21 October 2022
- Published by Springer Nature
- p. 137-153
Handling Polynomial and Transcendental Functions in SMT via Unconstrained Optimisation and Topological Degree Test
- 21 October 2022
- Published by Springer Nature
- p. 137-153
Handling Polynomial and Transcendental Functions in SMT via Unconstrained Optimisation and Topological Degree Test
- 1 September 2021
- Published by Springer Nature
- p. 213-231
Optimization Modulo Non-linear Arithmetic via Incremental Linearization
- 1 September 2021
- Published by Springer Nature
- p. 213-231
Optimization Modulo Non-linear Arithmetic via Incremental Linearization
- Open Access
- 23 July 2021
- Published by Springer Nature in Journal of Automated Reasoning
- Vol. 65 (7) , 1071-1096
Optimization Modulo the Theories of Signed Bit-Vectors and Floating-Point Numbers
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}}}$$ ) for the integers and that of floating-point numbers ( $$\mathcal {FP}$$ ) for the reals respectively. Whereas an approach for OMT with (unsigned) $${{\mathcal {B}}}{{\mathcal {V}}}$$ objectives has been proposed by Nadel & Ryvchin, unfortunately we are not aware of any existing approach for OMT with $$\mathcal {FP}$$ objectives. In this paper we fill this gap, and we address for the first time $$\text {OMT}$$ with $$\mathcal {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}}}$$ objectives and, most importantly, with $$\mathcal {FP}$$ objectives. We have implemented some novel $$\text {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.- 23 July 2021
- Published by Springer Nature in Journal of Automated Reasoning
- Vol. 65 (7) , 1071-1096
Open AccessOptimization Modulo the Theories of Signed Bit-Vectors and Floating-Point Numbers
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}}}$$ ) for the integers and that of floating-point numbers ( $$\mathcal {FP}$$ ) for the reals respectively. Whereas an approach for OMT with (unsigned) $${{\mathcal {B}}}{{\mathcal {V}}}$$ objectives has been proposed by Nadel & Ryvchin, unfortunately we are not aware of any existing approach for OMT with $$\mathcal {FP}$$ objectives. In this paper we fill this gap, and we address for the first time $$\text {OMT}$$ with $$\mathcal {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}}}$$ objectives and, most importantly, with $$\mathcal {FP}$$ objectives. We have implemented some novel $$\text {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. - 1 December 2020
- Published by Elsevier in Information and Computation
- Vol. 275
Solving SAT (and MaxSAT) with a quantum annealer: Foundations, encodings, and preliminary results
- 1 December 2020
- Published by Elsevier in Information and Computation
- Vol. 275
Solving SAT (and MaxSAT) with a quantum annealer: Foundations, encodings, and preliminary results