Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Efficiency of quantum vs. classical annealing in nonconvex learning problems.

ABSTRACT: Quantum annealers aim at solving nonconvex optimization problems by exploiting cooperative tunneling effects to escape local minima. The underlying idea consists of designing a classical energy function whose ground states are the sought optimal solutions of the original optimization problem and add a controllable quantum transverse field to generate tunneling processes. A key challenge is to identify classes of nonconvex optimization problems for which quantum annealing remains efficient while thermal annealing fails. We show that this happens for a wide class of problems which are central to machine learning. Their energy landscapes are dominated by local minima that cause exponential slowdown of classical thermal annealers while simulated quantum annealing converges efficiently to rare dense regions of optimal solutions.

SUBMITTER: Baldassi C

PROVIDER: S-EPMC5816144 | biostudies-literature | 2018 Feb

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Efficiency of quantum vs. classical annealing in nonconvex learning problems.

Baldassi Carlo C Zecchina Riccardo R

Proceedings of the National Academy of Sciences of the United States of America 20180130 7

Quantum annealers aim at solving nonconvex optimization problems by exploiting cooperative tunneling effects to escape local minima. The underlying idea consists of designing a classical energy function whose ground states are the sought optimal solutions of the original optimization problem and add a controllable quantum transverse field to generate tunneling processes. A key challenge is to identify classes of nonconvex optimization problems for which quantum annealing remains efficient while ...[more]

PMID: 29382764

Similar Datasets

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

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

OPTIMAL COMPUTATIONAL AND STATISTICAL RATES OF CONVERGENCE FOR SPARSE NONCONVEX LEARNING PROBLEMS.

Project description:We provide theoretical analysis of the statistical and computational properties of penalized M-estimators that can be formulated as the solution to a possibly nonconvex optimization problem. Many important estimators fall in this category, including least squares regression with nonconvex regularization, generalized linear models with nonconvex regularization and sparse elliptical random design regression. For these problems, it is intractable to calculate the global solution due to the nonconvex formulation. In this paper, we propose an approximate regularization path-following method for solving a variety of learning problems with nonconvex objective functions. Under a unified analytic framework, we simultaneously provide explicit statistical and computational rates of convergence for any local solution attained by the algorithm. Computationally, our algorithm attains a global geometric rate of convergence for calculating the full regularization path, which is optimal among all first-order algorithms. Unlike most existing methods that only attain geometric rates of convergence for one single regularization parameter, our algorithm calculates the full regularization path with the same iteration complexity. In particular, we provide a refined iteration complexity bound to sharply characterize the performance of each stage along the regularization path. Statistically, we provide sharp sample complexity analysis for all the approximate local solutions along the regularization path. In particular, our analysis improves upon existing results by providing a more refined sample complexity bound as well as an exact support recovery result for the final estimator. These results show that the final estimator attains an oracle statistical property due to the usage of nonconvex penalty.

| S-EPMC4276088 | biostudies-literature

Explaining the Efficiency of Photosynthesis: Quantum Uncertainty or Classical Vibrations?

Project description:Photosynthetic organisms are known to use a mechanism of vibrationally assisted exciton energy transfer to efficiently harvest energy from light. The importance of quantum effects in this mechanism is a long-standing topic of debate, which has traditionally focused on the role of excitonic coherences. Here, we address another recent claim: that the efficient energy transfer in the Fenna-Matthews-Olson complex relies on nuclear quantum uncertainty and would not function if the vibrations were classical. We present a counter-example to this claim, showing by trajectory-based simulations that a description in terms of quantum electrons and classical nuclei is indeed sufficient to describe the funneling of energy to the reaction center. We analyze and compare these findings to previous classical-nuclear approximations that predicted the absence of an energy funnel and conclude that the key difference and the reason for the discrepancy is the ability of the trajectories to properly account for Newton's third law.

| S-EPMC9036581 | biostudies-literature

Machine learning on quantum experimental data toward solving quantum many-body problems.

Project description:Advancements in the implementation of quantum hardware have enabled the acquisition of data that are intractable for emulation with classical computers. The integration of classical machine learning (ML) algorithms with these data holds potential for unveiling obscure patterns. Although this hybrid approach extends the class of efficiently solvable problems compared to using only classical computers, this approach has been only realized for solving restricted problems because of the prevalence of noise in current quantum computers. Here, we extend the applicability of the hybrid approach to problems of interest in many-body physics, such as predicting the properties of the ground state of a given Hamiltonian and classifying quantum phases. By performing experiments with various error-reducing procedures on superconducting quantum hardware with 127 qubits, we managed to acquire refined data from the quantum computer. This enabled us to demonstrate the successful implementation of theoretically suggested classical ML algorithms for systems with up to 44 qubits. Our results verify the scalability and effectiveness of the classical ML algorithms for processing quantum experimental data.

| S-EPMC11364692 | biostudies-literature

Quantum-classical simulations of rhodopsin reveal excited-state population splitting and its effects on quantum efficiency.

Project description:The activation of rhodopsin, the light-sensitive G-protein-coupled receptor responsible for dim-light vision in vertebrates, is driven by an ultrafast excited-state double-bond isomerization with a quantum efficiency of almost 70%. The origin of such light sensitivity is not understood and a key question is whether in-phase nuclear motion controls the quantum efficiency value. In this study we used hundreds of quantum-classical trajectories to show that, 15 fs after light absorption, a degeneracy between the reactive excited state and a neighbouring state causes the splitting of the rhodopsin population into subpopulations. These subpopulations propagate with different velocities and lead to distinct contributions to the quantum efficiency. We also show here that such splitting is modulated by protein electrostatics, thus linking amino acid sequence variations to quantum efficiency modulation. Finally, we discuss how such a linkage that in principle could be exploited to achieve higher quantum efficiencies would simultaneously increase the receptor thermal noise leading to a trade-off that may have played a role in rhodopsin evolution.

| S-EPMC8983576 | biostudies-literature

Optimizing High-Efficiency Quantum Memory with Quantum Machine Learning for Near-Term Quantum Devices.

Project description:Quantum memories are a fundamental of any global-scale quantum Internet, high-performance quantum networking and near-term quantum computers. A main problem of quantum memories is the low retrieval efficiency of the quantum systems from the quantum registers of the quantum memory. Here, we define a novel quantum memory called high-retrieval-efficiency (HRE) quantum memory for near-term quantum devices. An HRE quantum memory unit integrates local unitary operations on its hardware level for the optimization of the readout procedure and utilizes the advanced techniques of quantum machine learning. We define the integrated unitary operations of an HRE quantum memory, prove the learning procedure, and evaluate the achievable output signal-to-noise ratio values. We prove that the local unitaries of an HRE quantum memory achieve the optimization of the readout procedure in an unsupervised manner without the use of any labeled data or training sequences. We show that the readout procedure of an HRE quantum memory is realized in a completely blind manner without any information about the input quantum system or about the unknown quantum operation of the quantum register. We evaluate the retrieval efficiency of an HRE quantum memory and the output SNR (signal-to-noise ratio). The results are particularly convenient for gate-model quantum computers and the near-term quantum devices of the quantum Internet.

| S-EPMC6954268 | biostudies-literature

Superconducting quantum circuit of NOR in quantum annealing.

Project description:The applicability of quantum annealing to various problems can be improved by expressing the Hamiltonian using a circuit satisfiability problem. We investigate the detailed characteristics of the NOR/NAND functions of a superconducting quantum circuit, which are the basic building blocks to implementing various types of problem Hamiltonians. The circuit is composed of superconducting flux qubits with all-to-all connectivity, where direct magnetic couplers are utilized instead of the variable couplers in the conventional superconducting quantum circuit. This configuration provides efficient scalability because the problem Hamiltonian is implemented using fewer qubits. We present an experiment with a complete logic operation of NOR/NAND, in which the circuit produces results with a high probability of success for arbitrary combinations of inputs. The features of the quantum circuit agree qualitatively with the theory, especially the mechanism for an operation under external flux modulation. Moreover, by calibrating the bias conditions to compensate for the offset flux from the surrounding circuit, the quantum circuit quantitatively agrees with the theory. To achieve true quantum annealing, we discuss the effects of the reduction in electric noise in quantum annealing.

| S-EPMC9508137 | biostudies-literature

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

GLOBAL SOLUTIONS TO FOLDED CONCAVE PENALIZED NONCONVEX LEARNING.

Project description:This paper is concerned with solving nonconvex learning problems with folded concave penalty. Despite that their global solutions entail desirable statistical properties, there lack optimization techniques that guarantee global optimality in a general setting. In this paper, we show that a class of nonconvex learning problems are equivalent to general quadratic programs. This equivalence facilitates us in developing mixed integer linear programming reformulations, which admit finite algorithms that find a provably global optimal solution. We refer to this reformulation-based technique as the mixed integer programming-based global optimization (MIPGO). To our knowledge, this is the first global optimization scheme with a theoretical guarantee for folded concave penalized nonconvex learning with the SCAD penalty (Fan and Li, 2001) and the MCP penalty (Zhang, 2010). Numerical results indicate a significant outperformance of MIPGO over the state-of-the-art solution scheme, local linear approximation, and other alternative solution techniques in literature in terms of solution quality.

| S-EPMC4851172 | biostudies-other

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