Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Graph coloring using the reduced quantum genetic algorithm.

ABSTRACT: Genetic algorithms (GA) are computational methods for solving optimization problems inspired by natural selection. Because we can simulate the quantum circuits that implement GA in different highly configurable noise models and even run GA on actual quantum computers, we can analyze this class of heuristic methods in the quantum context for NP-hard problems. This paper proposes an instantiation of the Reduced Quantum Genetic Algorithm (RQGA) that solves the NP-hard graph coloring problem in O(N^1/2). The proposed implementation solves both vertex and edge coloring and can also determine the chromatic number (i.e., the minimum number of colors required to color the graph). We examine the results, analyze the algorithm convergence, and measure the algorithm's performance using the Qiskit simulation environment. Our Reduced Quantum Genetic Algorithm (RQGA) circuit implementation and the graph coloring results show that quantum heuristics can tackle complex computational problems more efficiently than their conventional counterparts.

SUBMITTER: Ardelean SM

PROVIDER: S-EPMC8771768 | biostudies-literature | 2022

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Graph coloring using the reduced quantum genetic algorithm.

Ardelean Sebastian Mihai SM Udrescu Mihai M

PeerJ. Computer science 20220103

Genetic algorithms (GA) are computational methods for solving optimization problems inspired by natural selection. Because we can simulate the quantum circuits that implement GA in different highly configurable noise models and even run GA on actual quantum computers, we can analyze this class of heuristic methods in the quantum context for NP-hard problems. This paper proposes an instantiation of the Reduced Quantum Genetic Algorithm (RQGA) that solves the NP-hard graph coloring problem in O(N< ...[more]

PMID: 35111921

Similar Datasets

Dynamic compression schemes for graph coloring.

Project description:MotivationTechnological advancements in high-throughput DNA sequencing have led to an exponential growth of sequencing data being produced and stored as a byproduct of biomedical research. Despite its public availability, a majority of this data remains hard to query for the research community due to a lack of efficient data representation and indexing solutions. One of the available techniques to represent read data is a condensed form as an assembly graph. Such a representation contains all sequence information but does not store contextual information and metadata.ResultsWe present two new approaches for a compressed representation of a graph coloring: a lossless compression scheme based on a novel application of wavelet tries as well as a highly accurate lossy compression based on a set of Bloom filters. Both strategies retain a coloring even when adding to the underlying graph topology. We present construction and merge procedures for both methods and evaluate their performance on a wide range of different datasets. By dropping the requirement of a fully lossless compression and using the topological information of the underlying graph, we can reduce memory requirements by up to three orders of magnitude. Representing individual colors as independently stored modules, our approaches can be efficiently parallelized and provide strategies for dynamic use. These properties allow for an easy upscaling to the problem sizes common to the biomedical domain.Availability and implementationWe provide prototype implementations in C++, summaries of our experiments as well as links to all datasets publicly at https://github.com/ratschlab/graph_annotation.Supplementary informationSupplementary data are available at Bioinformatics online.

| S-EPMC6530811 | biostudies-literature

Hybrid quantum search with genetic algorithm optimization.

Project description:Quantum genetic algorithms (QGA) integrate genetic programming and quantum computing to address search and optimization problems. The standard strategy of the hybrid QGA approach is to add quantum resources to classical genetic algorithms (GA), thus improving their efficacy (i.e., quantum optimization of a classical algorithm). However, the extent of such improvements is still unclear. Conversely, Reduced Quantum Genetic Algorithm (RQGA) is a fully quantum algorithm that reduces the GA search for the best fitness in a population of potential solutions to running Grover's algorithm. Unfortunately, RQGA finds the best fitness value and its corresponding chromosome (i.e., the solution or one of the solutions of the problem) in exponential runtime, O(2n/2), where n is the number of qubits in the individuals' quantum register. This article introduces a novel QGA optimization strategy, namely a classical optimization of a fully quantum algorithm, to address the RQGA complexity problem. Accordingly, we control the complexity of the RQGA algorithm by selecting a limited number of qubits in the individuals' register and fixing the remaining ones as classical values of '0' and '1' with a genetic algorithm. We also improve the performance of RQGA by discarding unfit solutions and bounding the search only in the area of valid individuals. As a result, our Hybrid Quantum Algorithm with Genetic Optimization (HQAGO) solves search problems in O(2(n-k)/2) oracle queries, where k is the number of fixed classical bits in the individuals' register.

| S-EPMC11639129 | biostudies-literature

Universal quantum simulation of single-qubit nonunitary operators using duality quantum algorithm.

Project description:Quantum information processing enhances human's power to simulate nature in quantum level and solve complex problem efficiently. During the process, a series of operators is performed to evolve the system or undertake a computing task. In recent year, research interest in non-Hermitian quantum systems, dissipative-quantum systems and new quantum algorithms has greatly increased, which nonunitary operators take an important role in. In this work, we utilize the linear combination of unitaries technique for nonunitary dynamics on a single qubit to give explicit decompositions of the necessary unitaries, and simulate arbitrary time-dependent single-qubit nonunitary operator F(t) using duality quantum algorithm. We find that the successful probability is not only decided by F(t) and the initial state, but also is inversely proportional to the dimensions of the used ancillary Hilbert subspace. In a general case, the simulation can be achieved in both eight- and six-dimensional Hilbert spaces. In phase matching conditions, F(t) can be simulated by only two qubits. We illustrate our method by simulating typical non-Hermitian systems and single-qubit measurements. Our method can be extended to high-dimensional case, such as Abrams-Lloyd's two-qubit gate. By discussing the practicability, we expect applications and experimental implementations in the near future.

| S-EPMC7889913 | biostudies-literature

A Robust Reduced Rank Graph Regression Method for Neuroimaging Genetic Analysis.

Project description:To characterize associations between genetic and neuroimaging data, a variety of analytic methods have been proposed in neuroimaging genetic studies. These methods have achieved promising performance by taking into account inherent correlation in either the neuroimaging data or the genetic data alone. In this study, we propose a novel robust reduced rank graph regression based method in a linear regression framework by considering correlations inherent in neuroimaging data and genetic data jointly. Particularly, we model the association analysis problem in a reduced rank regression framework with the genetic data as a feature matrix and the neuroimaging data as a response matrix by jointly considering correlations among the neuroimaging data as well as correlations between the genetic data and the neuroimaging data. A new graph representation of genetic data is adopted to exploit their inherent correlations, in addition to robust loss functions for both the regression and the data representation tasks, and a square-root-operator applied to the robust loss functions for achieving adaptive sample weighting. The resulting optimization problem is solved using an iterative optimization method whose convergence has been theoretically proved. Experimental results on the Alzheimer's Disease Neuroimaging Initiative (ADNI) dataset have demonstrated that our method could achieve competitive performance in terms of regression performance between brain structural measures and the Single Nucleotide Polymorphisms (SNPs), compared with state-of-the-art alternative methods.

| S-EPMC6092232 | biostudies-literature

Movie Review Summarization Using Supervised Learning and Graph-Based Ranking Algorithm.

Project description:With the growing information on web, online movie review is becoming a significant information resource for Internet users. However, online users post thousands of movie reviews on daily basis and it is hard for them to manually summarize the reviews. Movie review mining and summarization is one of the challenging tasks in natural language processing. Therefore, an automatic approach is desirable to summarize the lengthy movie reviews, and it will allow users to quickly recognize the positive and negative aspects of a movie. This study employs a feature extraction technique called bag of words (BoW) to extract features from movie reviews and represent the reviews as a vector space model or feature vector. The next phase uses Naïve Bayes machine learning algorithm to classify the movie reviews (represented as feature vector) into positive and negative. Next, an undirected weighted graph is constructed from the pairwise semantic similarities between classified review sentences in such a way that the graph nodes represent review sentences, while the edges of graph indicate semantic similarity weight. The weighted graph-based ranking algorithm (WGRA) is applied to compute the rank score for each review sentence in the graph. Finally, the top ranked sentences (graph nodes) are chosen based on highest rank scores to produce the extractive summary. Experimental results reveal that the proposed approach is superior to other state-of-the-art approaches.

| S-EPMC7288188 | biostudies-literature

Epitope mapping using combinatorial phage-display libraries: a graph-based algorithm.

Project description:A phage-display library of random peptides is a combinatorial experimental technique that can be harnessed for studying antibody-antigen interactions. In this technique, a phage peptide library is scanned against an antibody molecule to obtain a set of peptides that are bound by the antibody with high affinity. This set of peptides is regarded as mimicking the genuine epitope of the antibody's interacting antigen and can be used to define it. Here we present PepSurf, an algorithm for mapping a set of affinity-selected peptides onto the solved structure of the antigen. The problem of epitope mapping is converted into the task of aligning a set of query peptides to a graph representing the surface of the antigen. The best match of each peptide is found by aligning it against virtually all possible paths in the graph. Following a clustering step, which combines the most significant matches, a predicted epitope is inferred. We show that PepSurf accurately predicts the epitope in four cases for which the epitope is known from a solved antibody-antigen co-crystal complex. We further examine the capabilities of PepSurf for predicting other types of protein-protein interfaces. The performance of PepSurf is compared to other available epitope mapping programs.

| S-EPMC1761437 | biostudies-literature

A quantum-quantum Metropolis algorithm.

Project description:The classical Metropolis sampling method is a cornerstone of many statistical modeling applications that range from physics, chemistry, and biology to economics. This method is particularly suitable for sampling the thermal distributions of classical systems. The challenge of extending this method to the simulation of arbitrary quantum systems is that, in general, eigenstates of quantum Hamiltonians cannot be obtained efficiently with a classical computer. However, this challenge can be overcome by quantum computers. Here, we present a quantum algorithm which fully generalizes the classical Metropolis algorithm to the quantum domain. The meaning of quantum generalization is twofold: The proposed algorithm is not only applicable to both classical and quantum systems, but also offers a quantum speedup relative to the classical counterpart. Furthermore, unlike the classical method of quantum Monte Carlo, this quantum algorithm does not suffer from the negative-sign problem associated with fermionic systems. Applications of this algorithm include the study of low-temperature properties of quantum systems, such as the Hubbard model, and preparing the thermal states of sizable molecules to simulate, for example, chemical reactions at an arbitrary temperature.

| S-EPMC3271878 | biostudies-literature

Variational Quantum Algorithm for Non-Markovian Quantum Dynamics Using an Ensemble of Ehrenfest Trajectories.

Project description:The simulation of non-Markovian quantum dynamics plays an important role in the understanding of charge and exciton dynamics in the condensed phase environment, yet such a simulation remains computationally expensive on classical computers. In this work, we develop a variational quantum algorithm that is capable of simulating non-Markovian quantum dynamics on quantum computers. The algorithm captures the non-Markovian effect by employing the Ehrenfest trajectories and Monte Carlo sampling of their thermal distribution. We test the algorithm with the spin-boson model on the quantum simulator, and the results match quantitatively with the exact ones. The algorithm naturally fits into the parallel computing platform of the NISQ devices and can be extended to anharmonic system-bath interactions and multistate systems.

| S-EPMC11789130 | biostudies-literature

A parallel adaptive quantum genetic algorithm for the controllability of arbitrary networks.

Project description:In this paper, we propose a novel algorithm-parallel adaptive quantum genetic algorithm-which can rapidly determine the minimum control nodes of arbitrary networks with both control nodes and state nodes. The corresponding network can be fully controlled with the obtained control scheme. We transformed the network controllability issue into a combinational optimization problem based on the Popov-Belevitch-Hautus rank condition. A set of canonical networks and a list of real-world networks were experimented. Comparison results demonstrated that the algorithm was more ideal to optimize the controllability of networks, especially those larger-size networks. We demonstrated subsequently that there were links between the optimal control nodes and some network statistical characteristics. The proposed algorithm provides an effective approach to improve the controllability optimization of large networks or even extra-large networks with hundreds of thousands nodes.

| S-EPMC5858774 | biostudies-literature

Atom Identifiers Generated by a Neighborhood-Specific Graph Coloring Method Enable Compound Harmonization across Metabolic Databases.

Project description:Metabolic flux analysis requires both a reliable metabolic model and reliable metabolic profiles in characterizing metabolic reprogramming. Advances in analytic methodologies enable production of high-quality metabolomics datasets capturing isotopic flux. However, useful metabolic models can be difficult to derive due to the lack of relatively complete atom-resolved metabolic networks for a variety of organisms, including human. Here, we developed a neighborhood-specific graph coloring method that creates unique identifiers for each atom in a compound facilitating construction of an atom-resolved metabolic network. What is more, this method is guaranteed to generate the same identifier for symmetric atoms, enabling automatic identification of possible additional mappings caused by molecular symmetry. Furthermore, a compound coloring identifier derived from the corresponding atom coloring identifiers can be used for compound harmonization across various metabolic network databases, which is an essential first step in network integration. With the compound coloring identifiers, 8865 correspondences between KEGG (Kyoto Encyclopedia of Genes and Genomes) and MetaCyc compounds are detected, with 5451 of them confirmed by other identifiers provided by the two databases. In addition, we found that the Enzyme Commission numbers (EC) of reactions can be used to validate possible correspondence pairs, with 1848 unconfirmed pairs validated by commonality in reaction ECs. Moreover, we were able to detect various issues and errors with compound representation in KEGG and MetaCyc databases by compound coloring identifiers, demonstrating the usefulness of this methodology for database curation.

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