1
|
Ding J, Spallitta G, Sebastiani R. Effective prime factorization via quantum annealing by modular locally-structured embedding. Sci Rep 2024; 14:3518. [PMID: 38347002 PMCID: PMC10861481 DOI: 10.1038/s41598-024-53708-7] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/27/2023] [Accepted: 02/04/2024] [Indexed: 02/15/2024] Open
Abstract
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.
Collapse
Affiliation(s)
- Jingwen Ding
- Department of Computer Science and Engineering, University of Trento, Trento, Italy
| | - Giuseppe Spallitta
- Department of Computer Science and Engineering, University of Trento, Trento, Italy
| | - Roberto Sebastiani
- Department of Computer Science and Engineering, University of Trento, Trento, Italy.
| |
Collapse
|
2
|
Hudson RJ, MacDonald TSC, Cole JH, Schmidt TW, Smith TA, McCamey DR. A framework for multiexcitonic logic. Nat Rev Chem 2024:10.1038/s41570-023-00566-y. [PMID: 38273177 DOI: 10.1038/s41570-023-00566-y] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Accepted: 11/22/2023] [Indexed: 01/27/2024]
Abstract
Exciton science sits at the intersection of chemical, optical and spin-based implementations of information processing, but using excitons to conduct logical operations remains relatively unexplored. Excitons encoding information could be read optically (photoexcitation-photoemission) or electrically (charge recombination-separation), travel through materials via exciton energy transfer, and interact with one another in stimuli-responsive molecular excitonic devices. Excitonic logic offers the potential to mediate electrical, optical and chemical information. Additionally, high-spin triplet and quintet (multi)excitons offer access to well defined spin states of relevance to magnetic field effects, classical spintronics and spin-based quantum information science. In this Roadmap, we propose a framework for developing excitonic computing based on singlet fission (SF) and triplet-triplet annihilation (TTA). Various molecular components capable of modulating SF/TTA for logical operations are suggested, including molecular photo-switching and multi-colour photoexcitation. We then outline a pathway for constructing excitonic logic devices, considering aspects of circuit assembly, logical operation synchronization, and exciton transport and amplification. Promising future directions and challenges are identified, and the potential for realizing excitonic computing in the near future is discussed.
Collapse
Affiliation(s)
- Rohan J Hudson
- School of Chemistry, University of Melbourne, Melbourne, Victoria, Australia
- Australian Research Council Centre of Excellence in Exciton Science
| | - Thomas S C MacDonald
- Australian Research Council Centre of Excellence in Exciton Science
- School of Physics, UNSW Sydney, Sydney, New South Wales, Australia
| | - Jared H Cole
- Australian Research Council Centre of Excellence in Exciton Science
- School of Science, RMIT University, Melbourne, Victoria, Australia
| | - Timothy W Schmidt
- Australian Research Council Centre of Excellence in Exciton Science
- School of Chemistry, UNSW Sydney, Sydney, New South Wales, Australia
| | - Trevor A Smith
- School of Chemistry, University of Melbourne, Melbourne, Victoria, Australia
- Australian Research Council Centre of Excellence in Exciton Science
| | - Dane R McCamey
- Australian Research Council Centre of Excellence in Exciton Science, .
- School of Physics, UNSW Sydney, Sydney, New South Wales, Australia.
| |
Collapse
|
3
|
Srivastava S, Sundararaghavan V. Generative and discriminative training of Boltzmann machine through quantum annealing. Sci Rep 2023; 13:7889. [PMID: 37193710 DOI: 10.1038/s41598-023-34652-4] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/11/2023] [Accepted: 05/04/2023] [Indexed: 05/18/2023] Open
Abstract
A hybrid quantum-classical method for learning Boltzmann machines (BM) for a generative and discriminative task is presented. BM are undirected graphs with a network of visible and hidden nodes where the former is used as the reading site. In contrast, the latter is used to manipulate visible states' probability. In Generative BM, the samples of visible data imitate the probability distribution of a given data set. In contrast, the visible sites of discriminative BM are treated as Input/Output (I/O) reading sites where the conditional probability of output state is optimized for a given set of input states. The cost function for learning BM is defined as a weighted sum of Kullback-Leibler (KL) divergence and Negative conditional Log-likelihood (NCLL), adjusted using a hyper-parameter. Here, the KL Divergence is the cost for generative learning, and NCLL is the cost for discriminative learning. A Stochastic Newton-Raphson optimization scheme is presented. The gradients and the Hessians are approximated using direct samples of BM obtained through quantum annealing. Quantum annealers are hardware representing the physics of the Ising model that operates on low but finite temperatures. This temperature affects the probability distribution of the BM; however, its value is unknown. Previous efforts have focused on estimating this unknown temperature through regression of theoretical Boltzmann energies of sampled states with the probability of states sampled by the actual hardware. These approaches assume that the control parameter change does not affect the system temperature; however, this is usually untrue. Instead of using energies, the probability distribution of samples is employed to estimate the optimal parameter set, ensuring that the optimal set can be obtained from a single set of samples. The KL divergence and NCLL are optimized for the system temperature, and the result is used to rescale the control parameter set. The performance of this approach, as tested against the theoretically expected distributions, shows promising results for Boltzmann training on quantum annealers.
Collapse
|
4
|
Sandt R, Le Bouar Y, Spatschek R. Quantum annealing for microstructure equilibration with long-range elastic interactions. Sci Rep 2023; 13:6036. [PMID: 37055543 PMCID: PMC10102158 DOI: 10.1038/s41598-023-33232-w] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/24/2023] [Accepted: 04/10/2023] [Indexed: 04/15/2023] Open
Abstract
We demonstrate the use and benefits of quantum annealing approaches for the determination of equilibrated microstructures in shape memory alloys and other materials with long-range elastic interaction between coherent grains and their different martensite variants and phases. After a one dimensional illustration of the general approach, which requires to formulate the energy of the system in terms of an Ising Hamiltonian, we use distant dependent elastic interactions between grains to predict the variant selection for different transformation eigenstrains. The results and performance of the computations are compared to classical algorithms, demonstrating that the new approach can lead to a significant acceleration of the simulations. Beyond a discretization using simple cuboidal elements, also a direct representation of arbitrary microstructures is possible, allowing fast simulations with currently up to several thousand grains.
Collapse
Affiliation(s)
- Roland Sandt
- Structure and Function of Materials, Institute of Energy and Climate Research, Forschungszentrum Jülich GmbH, 52425, Jülich, Germany.
| | - Yann Le Bouar
- Université Paris-Saclay, ONERA, CNRS, Laboratoire d'Etude des Microstructures, 92320, Châtillon, France
| | - Robert Spatschek
- Structure and Function of Materials, Institute of Energy and Climate Research, Forschungszentrum Jülich GmbH, 52425, Jülich, Germany
- JARA-ENERGY, 52425, Jülich, Germany
| |
Collapse
|
5
|
Quantum computing reduces systemic risk in financial networks. Sci Rep 2023; 13:3990. [PMID: 36894579 PMCID: PMC9998608 DOI: 10.1038/s41598-023-30710-z] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/19/2022] [Accepted: 02/28/2023] [Indexed: 03/11/2023] Open
Abstract
In highly connected financial networks, the failure of a single institution can cascade into additional bank failures. This systemic risk can be mitigated by adjusting the loans, holding shares, and other liabilities connecting institutions in a way that prevents cascading of failures. We are approaching the systemic risk problem by attempting to optimize the connections between the institutions. In order to provide a more realistic simulation environment, we have incorporated nonlinear/discontinuous losses in the value of the banks. To address scalability challenges, we have developed a two-stage algorithm where the networks are partitioned into modules of highly interconnected banks and then the modules are individually optimized. We developed a new algorithms for classical and quantum partitioning for directed and weighed graphs (first stage) and a new methodology for solving Mixed Integer Linear Programming problems with constraints for the systemic risk context (second stage). We compare classical and quantum algorithms for the partitioning problem. Experimental results demonstrate that our two-stage optimization with quantum partitioning is more resilient to financial shocks, delays the cascade failure phase transition, and reduces the total number of failures at convergence under systemic risks with reduced time complexity.
Collapse
|
6
|
Wierzbiński M, Falcó-Roget J, Crimi A. Community detection in brain connectomes with hybrid quantum computing. Sci Rep 2023; 13:3446. [PMID: 36859591 PMCID: PMC9977923 DOI: 10.1038/s41598-023-30579-y] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/21/2022] [Accepted: 02/27/2023] [Indexed: 03/03/2023] Open
Abstract
Recent advancements in network neuroscience are pointing in the direction of considering the brain as a small-world system with an efficient integration-segregation balance that facilitates different cognitive tasks and functions. In this context, community detection is a pivotal issue in computational neuroscience. In this paper we explored community detection within brain connectomes using the power of quantum annealers, and in particular the Leap's Hybrid Solver in D-Wave. By reframing the modularity optimization problem into a Discrete Quadratic Model, we show that quantum annealers achieved higher modularity indices compared to the Louvain Community Detection Algorithm without the need to overcomplicate the mathematical formulation. We also found that the number of communities detected in brain connectomes slightly differed while still being biologically interpretable. These promising preliminary results, together with recent findings, strengthen the claim that quantum optimization methods might be a suitable alternative against classical approaches when dealing with community assignment in networks.
Collapse
Affiliation(s)
- Marcin Wierzbiński
- grid.425010.20000 0001 2286 5863University of Warsaw, Institute of Mathematics, Warsaw, 02-097 Poland ,Sano Center for Compuational Personalised Medicine, Computer Vision Group, Krakow, 30-054 Poland
| | - Joan Falcó-Roget
- Sano Center for Compuational Personalised Medicine, Computer Vision Group, Krakow, 30-054 Poland
| | - Alessandro Crimi
- Sano Center for Compuational Personalised Medicine, Computer Vision Group, Krakow, 30-054, Poland.
| |
Collapse
|
7
|
Suzuki S, Oshiyama H, Shibata N. Statistics of the number of defects after quantum annealing in a thermal environment. PHILOSOPHICAL TRANSACTIONS. SERIES A, MATHEMATICAL, PHYSICAL, AND ENGINEERING SCIENCES 2023; 381:20210411. [PMID: 36463929 DOI: 10.1098/rsta.2021.0411] [Citation(s) in RCA: 1] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Received: 07/25/2022] [Accepted: 09/30/2022] [Indexed: 06/17/2023]
Abstract
We study the statistics of the kink number generated by quantum annealing in a one-dimensional transverse Ising model coupled to a bosonic thermal bath. Using the freezing ansatz for quantum annealing in the thermal environment, we show the relation between the ratio of the second to the first cumulant of the kink number distribution and the average kink density. The theoretical result is confirmed thoroughly by numerical simulation using the non-Markovian infinite time-evolving block decimation which we proposed recently. The simulation using D-Wave's quantum annealer is also discussed. This article is part of the theme issue 'Quantum annealing and computation: challenges and perspectives'.
Collapse
Affiliation(s)
- Sei Suzuki
- Department of Liberal Arts, Saitama Medical University, Moroyama, Saitama, Japan
| | - Hiroki Oshiyama
- Department of Information Sciences, Tohoku University, Sendai, Japan
| | | |
Collapse
|
8
|
Chakrabarti BK, Leschke H, Ray P, Shirai T, Tanaka S. Quantum annealing and computation: challenges and perspectives. PHILOSOPHICAL TRANSACTIONS. SERIES A, MATHEMATICAL, PHYSICAL, AND ENGINEERING SCIENCES 2023; 381:20210419. [PMID: 36463926 PMCID: PMC9719792 DOI: 10.1098/rsta.2021.0419] [Citation(s) in RCA: 1] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Subscribe] [Scholar Register] [Received: 10/11/2022] [Accepted: 10/11/2022] [Indexed: 06/17/2023]
Abstract
In the introductory article of this theme issue, we provide an overview of quantum annealing and computation with a very brief summary of the individual contributions to this issue made by experts as well as a few young researchers. We hope the readers will get the touch of the excitement as well as the perspectives in this unusually active field and important developments there. This article is part of the theme issue 'Quantum annealing and computation: challenges and perspectives'.
Collapse
Affiliation(s)
- Bikas K. Chakrabarti
- Saha Institute of Nuclear Physics, Kolkata 700064, India
- Indian Statistical Institute, Kolkata 700108, India
| | - Hajo Leschke
- Institut für Theoretische Physik, Universität Erlangen-Nürnberg, 91058 Erlangen, Germany
| | - Purusattam Ray
- The Institute of Mathematical Sciences, Taramani, Chennai 600113, India
| | - Tatsuhiko Shirai
- Department of Computer Science and Communications Engineering, Waseda University, Tokyo 169-8555, Japan
| | - Shu Tanaka
- Department of Applied Physics and Physico-Informatics, Keio University, Yokohama 223-8522, Japan
| |
Collapse
|