Browse
Submit Data
Databases
API
Help

Dataset Information

25 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Ultrafast adiabatic quantum algorithm for the NP-complete exact cover problem.

ABSTRACT: An adiabatic quantum algorithm may lose quantumness such as quantum coherence entirely in its long runtime, and consequently the expected quantum speedup of the algorithm does not show up. Here we present a general ultrafast adiabatic quantum algorithm. We show that by applying a sequence of fast random or regular signals during evolution, the runtime can be reduced substantially, whereas advantages of the adiabatic algorithm remain intact. We also propose a randomized Trotter formula and show that the driving Hamiltonian and the proposed sequence of fast signals can be implemented simultaneously. We illustrate the algorithm by solving the NP-complete 3-bit exact cover problem (EC3), where NP stands for nondeterministic polynomial time, and put forward an approach to implementing the problem with trapped ions.

SUBMITTER: Wang H

PROVIDER: S-EPMC4770423 | biostudies-other | 2016

REPOSITORIES: biostudies-other

ACCESS DATA

Json Xml

Similar Datasets

An Efficient Exact Quantum Algorithm for the Integer Square-free Decomposition Problem.

Project description:Quantum computers are known to be qualitatively more powerful than classical computers, but so far only a small number of different algorithms have been discovered that actually use this potential. It would therefore be highly desirable to develop other types of quantum algorithms that widen the range of possible applications. Here we propose an efficient and exact quantum algorithm for finding the square-free part of a large integer - a problem for which no efficient classical algorithm exists. The algorithm relies on properties of Gauss sums and uses the quantum Fourier transform. We give an explicit quantum network for the algorithm. Our algorithm introduces new concepts and methods that have not been used in quantum information processing so far and may be applicable to a wider class of problems.

| S-EPMC3277347 | biostudies-literature

An exact algorithm for finding cancer driver somatic genome alterations: the weighted mutually exclusive maximum set cover problem.

Project description:BackgroundThe mutual exclusivity of somatic genome alterations (SGAs), such as somatic mutations and copy number alterations, is an important observation of tumors and is widely used to search for cancer signaling pathways or SGAs related to tumor development. However, one problem with current methods that use mutual exclusivity is that they are not signal-based; another problem is that they use heuristic algorithms to handle the NP-hard problems, which cannot guarantee to find the optimal solutions of their models.MethodIn this study, we propose a novel signal-based method that utilizes the intrinsic relationship between SGAs on signaling pathways and expression changes of downstream genes regulated by pathways to identify cancer signaling pathways using the mutually exclusive property. We also present a relatively efficient exact algorithm that can guarantee to obtain the optimal solution of the new computational model.ResultsWe have applied our new model and exact algorithm to the breast cancer data. The results reveal that our new approach increases the capability of finding better solutions in the application of cancer research. Our new exact algorithm has a time complexity of [Formula: see text](Note: Following the recent convention, we use a star * to represent that the polynomial part of the time complexity is neglected), which has solved the NP-hard problem of our model efficiently.ConclusionOur new method and algorithm can discover the true causes behind the phenotypes, such as what SGA events lead to abnormality of the cell cycle or make the cell metastasis lose control in tumors; thus, it identifies the target candidates for precision (or target) therapeutics.

| S-EPMC4855522 | 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

An adaptive variational algorithm for exact molecular simulations on a quantum computer.

Project description:Quantum simulation of chemical systems is one of the most promising near-term applications of quantum computers. The variational quantum eigensolver, a leading algorithm for molecular simulations on quantum hardware, has a serious limitation in that it typically relies on a pre-selected wavefunction ansatz that results in approximate wavefunctions and energies. Here we present an arbitrarily accurate variational algorithm that, instead of fixing an ansatz upfront, grows it systematically one operator at a time in a way dictated by the molecule being simulated. This generates an ansatz with a small number of parameters, leading to shallow-depth circuits. We present numerical simulations, including for a prototypical strongly correlated molecule, which show that our algorithm performs much better than a unitary coupled cluster approach, in terms of both circuit depth and chemical accuracy. Our results highlight the potential of our adaptive algorithm for exact simulations with present-day and near-term quantum hardware.

| S-EPMC6614426 | biostudies-literature

Adiabatic quantum simulation of quantum chemistry.

Project description:We show how to apply the quantum adiabatic algorithm directly to the quantum computation of molecular properties. We describe a procedure to map electronic structure Hamiltonians to 2-body qubit Hamiltonians with a small set of physically realizable couplings. By combining the Bravyi-Kitaev construction to map fermions to qubits with perturbative gadgets to reduce the Hamiltonian to 2-body, we obtain precision requirements on the coupling strengths and a number of ancilla qubits that scale polynomially in the problem size. Hence our mapping is efficient. The required set of controllable interactions includes only two types of interaction beyond the Ising interactions required to apply the quantum adiabatic algorithm to combinatorial optimization problems. Our mapping may also be of interest to chemists directly as it defines a dictionary from electronic structure to spin Hamiltonians with physical interactions.

| S-EPMC4194464 | biostudies-other

Adiabatic quantum state transfer in a semiconductor quantum-dot spin chain.

Project description:Semiconductor quantum-dot spin qubits are a promising platform for quantum computation, because they are scalable and possess long coherence times. In order to realize this full potential, however, high-fidelity information transfer mechanisms are required for quantum error correction and efficient algorithms. Here, we present evidence of adiabatic quantum-state transfer in a chain of semiconductor quantum-dot electron spins. By adiabatically modifying exchange couplings, we transfer single- and two-spin states between distant electrons in less than 127 ns. We also show that this method can be cascaded for spin-state transfer in long spin chains. Based on simulations, we estimate that the probability to correctly transfer single-spin eigenstates and two-spin singlet states can exceed 0.95 for the experimental parameters studied here. In the future, state and process tomography will be required to verify the transfer of arbitrary single qubit states with a fidelity exceeding the classical bound. Adiabatic quantum-state transfer is robust to noise and pulse-timing errors. This method will be useful for initialization, state distribution, and readout in large spin-qubit arrays for gate-based quantum computing. It also opens up the possibility of universal adiabatic quantum computing in semiconductor quantum-dot spin qubits.

| S-EPMC8042124 | biostudies-literature

A complete hierarchy for the pure state marginal problem in quantum mechanics.

Project description:Clarifying the relation between the whole and its parts is crucial for many problems in science. In quantum mechanics, this question manifests itself in the quantum marginal problem, which asks whether there is a global pure quantum state for some given marginals. This problem arises in many contexts, ranging from quantum chemistry to entanglement theory and quantum error correcting codes. In this paper, we prove a correspondence of the marginal problem to the separability problem. Based on this, we describe a sequence of semidefinite programs which can decide whether some given marginals are compatible with some pure global quantum state. As an application, we prove that the existence of multiparticle absolutely maximally entangled states for a given dimension is equivalent to the separability of an explicitly given two-party quantum state. Finally, we show that the existence of quantum codes with given parameters can also be interpreted as a marginal problem, hence, our complete hierarchy can also be used.

| S-EPMC7881147 | biostudies-literature

More bang for your buck: super-adiabatic quantum engines.

Project description:The practical untenability of the quasi-static assumption makes any realistic engine intrinsically irreversible and its operating time finite, thus implying friction effects at short cycle times. An important technological goal is thus the design of maximally efficient engines working at the maximum possible power. We show that, by utilising shortcuts to adiabaticity in a quantum engine cycle, one can engineer a thermodynamic cycle working at finite power and zero friction. Our findings are illustrated using a harmonic oscillator undergoing a quantum Otto cycle.

| S-EPMC4147366 | biostudies-literature

Kraken: ultrafast metagenomic sequence classification using exact alignments.

Project description:Kraken is an ultrafast and highly accurate program for assigning taxonomic labels to metagenomic DNA sequences. Previous programs designed for this task have been relatively slow and computationally expensive, forcing researchers to use faster abundance estimation programs, which only classify small subsets of metagenomic data. Using exact alignment of k-mers, Kraken achieves classification accuracy comparable to the fastest BLAST program. In its fastest mode, Kraken classifies 100 base pair reads at a rate of over 4.1 million reads per minute, 909 times faster than Megablast and 11 times faster than the abundance estimation program MetaPhlAn. Kraken is available at http://ccb.jhu.edu/software/kraken/.

| S-EPMC4053813 | biostudies-other

Bifurcation-based adiabatic quantum computation with a nonlinear oscillator network.

Project description:The dynamics of nonlinear systems qualitatively change depending on their parameters, which is called bifurcation. A quantum-mechanical nonlinear oscillator can yield a quantum superposition of two oscillation states, known as a Schrödinger cat state, via quantum adiabatic evolution through its bifurcation point. Here we propose a quantum computer comprising such quantum nonlinear oscillators, instead of quantum bits, to solve hard combinatorial optimization problems. The nonlinear oscillator network finds optimal solutions via quantum adiabatic evolution, where nonlinear terms are increased slowly, in contrast to conventional adiabatic quantum computation or quantum annealing, where quantum fluctuation terms are decreased slowly. As a result of numerical simulations, it is concluded that quantum superposition and quantum fluctuation work effectively to find optimal solutions. It is also notable that the present computer is analogous to neural computers, which are also networks of nonlinear components. Thus, the present scheme will open new possibilities for quantum computation, nonlinear science, and artificial intelligence.

| S-EPMC4761947 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

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