Browse
Submit Data
Databases
API
Help

Dataset Information

20 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Prime factorization using quantum annealing and computational algebraic geometry.

ABSTRACT: We investigate prime factorization from two perspectives: quantum annealing and computational algebraic geometry, specifically Gröbner bases. We present a novel autonomous algorithm which combines the two approaches and leads to the factorization of all bi-primes up to just over 200000, the largest number factored to date using a quantum processor. We also explain how Gröbner bases can be used to reduce the degree of Hamiltonians.

SUBMITTER: Dridi R

PROVIDER: S-EPMC5318873 | biostudies-literature | 2017 Feb

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Prime factorization using quantum annealing and computational algebraic geometry.

Dridi Raouf R Alghassi Hedayat H

Scientific reports 20170221

We investigate prime factorization from two perspectives: quantum annealing and computational algebraic geometry, specifically Gröbner bases. We present a novel autonomous algorithm which combines the two approaches and leads to the factorization of all bi-primes up to just over 200000, the largest number factored to date using a quantum processor. We also explain how Gröbner bases can be used to reduce the degree of Hamiltonians. ...[more]

PMID: 28220854

Similar Datasets

Quantum Annealing for Prime Factorization.

Project description:We have developed a framework to convert an arbitrary integer factorization problem to an executable Ising model by first writing it as an optimization function then transforming the k-bit coupling (k ? 3) terms to quadratic terms using ancillary variables. Our resource-efficient method uses [Formula: see text] binary variables (qubits) for finding the factors of an integer N. We present how to factorize 15, 143, 59989, and 376289 using 4, 12, 59, and 94 logical qubits, respectively. This method was tested using the D-Wave 2000Q for finding an embedding and determining the prime factors for a given composite number. The method is general and could be used to factor larger integers as the number of available qubits increases, or combined with other ad hoc methods to achieve better performances for specific numbers.

| S-EPMC6281593 | biostudies-literature

Prime factorization using quantum variational imaginary time evolution.

Project description:The road to computing on quantum devices has been accelerated by the promises that come from using Shor's algorithm to reduce the complexity of prime factorization. However, this promise hast not yet been realized due to noisy qubits and lack of robust error correction schemes. Here we explore a promising, alternative method for prime factorization that uses well-established techniques from variational imaginary time evolution. We create a Hamiltonian whose ground state encodes the solution to the problem and use variational techniques to evolve a state iteratively towards these prime factors. We show that the number of circuits evaluated in each iteration scales as [Formula: see text], where n is the bit-length of the number to be factorized and d is the depth of the circuit. We use a single layer of entangling gates to factorize 36 numbers represented using 7, 8, and 9-qubit Hamiltonians. We also verify the method's performance by implementing it on the IBMQ Lima hardware to factorize 55, 65, 77 and 91 which are greater than the largest number (21) to have been factorized on IBMQ hardware.

| S-EPMC8531006 | biostudies-literature

A quantum-inspired probabilistic prime factorization based on virtually connected Boltzmann machine and probabilistic annealing.

Project description:Probabilistic computing has been introduced to operate functional networks using a probabilistic bit (p-bit), broadening the computational abilities in non-deterministic polynomial searching operations. However, previous developments have focused on emulating the operation of quantum computers similarly, implementing every p-bit with large weight-sum matrix multiplication blocks and requiring tens of times more p-bits than semiprime bits. In addition, operations based on a conventional simulated annealing scheme required a large number of sampling operations, which deteriorated the performance of the Ising machines. Here we introduce a prime factorization machine with a virtually connected Boltzmann machine and probabilistic annealing method, which are designed to reduce the hardware complexity and number of sampling operations. From 10-bit to 64-bit prime factorizations were performed, and the machine offers up to 1.2 × 108 times improvement in the number of sampling operations compared with previous factorization machines, with a 22-fold smaller hardware resource.

| S-EPMC10533543 | biostudies-literature

Factorization by quantum annealing using superconducting flux qubits implementing a multiplier Hamiltonian.

Project description:Prime factorization (P = M × N) is a promising application for quantum computing. Shor's algorithm is a key concept for breaking the limit for analyzing P, which cannot be effectively solved by classical computation; however, the algorithm requires error-correctable logical qubits. Here, we describe a quantum annealing method for solving prime factorization. A superconducting quantum circuit with native implementation of the multiplier Hamiltonian provides combinations of M and N as a solution for number P after annealing. This circuit is robust and can be expanded easily to scale up the analysis. We present an experimental and theoretical exploration of the multiplier unit. We demonstrate the 2-bit factorization in a circuit simulation and experimentally at 10 mK. We also explain how the current conditions can be used to obtain high success probability and all candidate factorized elements.

| S-EPMC9372081 | biostudies-literature

Identifiability and numerical algebraic geometry.

Project description:A common problem when analyzing models, such as mathematical modeling of a biological process, is to determine if the unknown parameters of the model can be determined from given input-output data. Identifiable models are models such that the unknown parameters can be determined to have a finite number of values given input-output data. The total number of such values over the complex numbers is called the identifiability degree of the model. Unidentifiable models are models such that the unknown parameters can have an infinite number of values given input-output data. For unidentifiable models, a set of identifiable functions of the parameters are sought so that the model can be reparametrized in terms of these functions yielding an identifiable model. In this work, we use numerical algebraic geometry to determine if a model given by polynomial or rational ordinary differential equations is identifiable or unidentifiable. For identifiable models, we present a novel approach to compute the identifiability degree. For unidentifiable models, we present a novel numerical differential algebra technique aimed at computing a set of algebraically independent identifiable functions. Several examples are used to demonstrate the new techniques.

| S-EPMC6910699 | biostudies-literature

An analytical approach to bistable biological circuit discrimination using real algebraic geometry.

Project description:Biomolecular circuits with two distinct and stable steady states have been identified as essential components in a wide range of biological networks, with a variety of mechanisms and topologies giving rise to their important bistable property. Understanding the differences between circuit implementations is an important question, particularly for the synthetic biologist faced with determining which bistable circuit design out of many is best for their specific application. In this work we explore the applicability of Sturm's theorem--a tool from nineteenth-century real algebraic geometry--to comparing 'functionally equivalent' bistable circuits without the need for numerical simulation. We first consider two genetic toggle variants and two different positive feedback circuits, and show how specific topological properties present in each type of circuit can serve to increase the size of the regions of parameter space in which they function as switches. We then demonstrate that a single competitive monomeric activator added to a purely monomeric (and otherwise monostable) mutual repressor circuit is sufficient for bistability. Finally, we compare our approach with the Routh-Hurwitz method and derive consistent, yet more powerful, parametric conditions. The predictive power and ease of use of Sturm's theorem demonstrated in this work suggest that algebraic geometric techniques may be underused in biomolecular circuit analysis.

| S-EPMC4528596 | biostudies-literature

HUBO and QUBO models for prime factorization.

Project description:The security of the RSA cryptosystem is based on the difficulty of factoring a large number N into prime numbers [Formula: see text] and [Formula: see text] satisfying [Formula: see text]. This paper presents a prime factorization method using a D-Wave quantum computer that could threaten the RSA cryptosystem in the future. The starting point for this method is very simple, representing two prime numbers as qubits. Then, we set the difference between the product of the two prime numbers expressed in qubits and N as a cost function, and we find the solution when the cost function is minimized. D-Wave's quantum annealer can find the minimum value of any quadratic problem. However, the cost function must be a higher-order unconstrained optimization (HUBO) model because it contains second- or higher-order terms. We used a hybrid solver accessible via Leap, D-Wave's real-time quantum cloud service, and the dimod package provided by the D-Wave Ocean software development kit (SDK) to solve the HUBO problem. We also successfully factorized 102,454,763 with 26 logical qubits. In addition, we factorized 1,000,070,001,221 using the range-dependent Hamiltonian algorithm.

| S-EPMC10284802 | biostudies-literature

Quantum annealing versus classical machine learning applied to a simplified computational biology problem.

Project description:Transcription factors regulate gene expression, but how these proteins recognize and specifically bind to their DNA targets is still debated. Machine learning models are effective means to reveal interaction mechanisms. Here we studied the ability of a quantum machine learning approach to predict binding specificity. Using simplified datasets of a small number of DNA sequences derived from actual binding affinity experiments, we trained a commercially available quantum annealer to classify and rank transcription factor binding. The results were compared to state-of-the-art classical approaches for the same simplified datasets, including simulated annealing, simulated quantum annealing, multiple linear regression, LASSO, and extreme gradient boosting. Despite technological limitations, we find a slight advantage in classification performance and nearly equal ranking performance using the quantum annealer for these fairly small training data sets. Thus, we propose that quantum annealing might be an effective method to implement machine learning for certain computational biology problems.

| S-EPMC5891835 | biostudies-literature

Solving Set Cover with Pairs Problem using Quantum Annealing.

Project description:Here we consider using quantum annealing to solve Set Cover with Pairs (SCP), an NP-hard combinatorial optimization problem that plays an important role in networking, computational biology, and biochemistry. We show an explicit construction of Ising Hamiltonians whose ground states encode the solution of SCP instances. We numerically simulate the time-dependent Schrödinger equation in order to test the performance of quantum annealing for random instances and compare with that of simulated annealing. We also discuss explicit embedding strategies for realizing our Hamiltonian construction on the D-wave type restricted Ising Hamiltonian based on Chimera graphs. Our embedding on the Chimera graph preserves the structure of the original SCP instance and in particular, the embedding for general complete bipartite graphs and logical disjunctions may be of broader use than that the specific problem we deal with.

| S-EPMC5037405 | biostudies-literature

Reinforcement Quantum Annealing: A Hybrid Quantum Learning Automata.

Project description:We introduce the notion of reinforcement quantum annealing (RQA) scheme in which an intelligent agent searches in the space of Hamiltonians and interacts with a quantum annealer that plays the stochastic environment role of learning automata. At each iteration of RQA, after analyzing results (samples) from the previous iteration, the agent adjusts the penalty of unsatisfied constraints and re-casts the given problem to a new Ising Hamiltonian. As a proof-of-concept, we propose a novel approach for casting the problem of Boolean satisfiability (SAT) to Ising Hamiltonians and show how to apply the RQA for increasing the probability of finding the global optimum. Our experimental results on two different benchmark SAT problems (namely factoring pseudo-prime numbers and random SAT with phase transitions), using a D-Wave 2000Q quantum processor, demonstrated that RQA finds notably better solutions with fewer samples, compared to the best-known techniques in the realm of quantum annealing.

| S-EPMC7224393 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data