Ultrafast adiabatic quantum algorithm for the NP-complete exact cover problem.
Ontology highlight
ABSTRACT:
SUBMITTER: Wang H
PROVIDER: S-EPMC4770423 | biostudies-other | 2016
REPOSITORIES: biostudies-other
Similar Datasets
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
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
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
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
Project description:With a probability of success of 95% we solve the separability problem for Bell diagonal qutrit states with positive partial transposition (PPT). The separability problem, i.e. distinguishing separable and entangled states, generally lacks an efficient solution due to the existence of bound entangled states. In contrast to free entangled states that can be used for entanglement distillation via local operations and classical communication, these states cannot be detected by the Peres-Horodecki criterion or PPT criterion. We analyze a large family of bipartite qutrit states that can be separable, free entangled or bound entangled. Leveraging a geometrical representation of these states in Euclidean space, novel methods are presented that allow the classification of separable and bound entangled Bell diagonal states in an efficient way. Moreover, the classification allows the precise determination of relative volumes of the classes of separable, free and bound entangled states. In detail, out of all Bell diagonal PPT states [Formula: see text] are determined to be separable while [Formula: see text] are bound entangled and only [Formula: see text] remain unclassified. Moreover, our applied criteria are compared for their effectiveness and relation as detectors of bound entanglement, which reveals that not a single criterion is capable to detect all bound entangled states.
| S-EPMC9304426 | biostudies-literature
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
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
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
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
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