Multi-sequence alignment using the Quantum Approximate Optimization Algorithm
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913806125367296 |
|---|---|
| author | Madsen, Sebastian Yde Marqversen, Frederik Kofoed Rasmussen, Stig Elkjær Zinner, Nikolaj Thomas |
| author_facet | Madsen, Sebastian Yde Marqversen, Frederik Kofoed Rasmussen, Stig Elkjær Zinner, Nikolaj Thomas |
| contents | The task of Multiple Sequence Alignment (MSA) is a constrained combinatorial optimization problem that is generally considered a complex computational problem. In this paper, we first present a binary encoding of MSA and devise a corresponding soft-constrained cost-function that enables a Hamiltonian formulation and implementation of the MSA problem with the variational Quantum Approximate Optimization Algorithm (QAOA). Through theoretical analysis, a bound on the ratio of the number of feasible states to the size of the Hilbert space is determined. Furthermore, we consider a small instance of our QAOA-MSA algorithm in both a quantum simulator and its performance on an actual quantum computer. While the ideal solution to the instance of MSA investigated is shown to be the most probable state sampled for a shallow p<5 quantum circuit in the simulation, the level of noise in current devices is still a formidable challenge for the kind of MSA-QAOA algorithm developed here. In turn, we are not able to distinguish the feasible solutions from other states in the quantum hardware output data at this point. This indicates a need for further investigation into both the strategy utilized for compiling the quantum circuit, but also the possibility of devising a more compact ansatz, as one might achieve through constraint-preserving mixers for QAOA. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_12103 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Multi-sequence alignment using the Quantum Approximate Optimization Algorithm Madsen, Sebastian Yde Marqversen, Frederik Kofoed Rasmussen, Stig Elkjær Zinner, Nikolaj Thomas Quantum Physics The task of Multiple Sequence Alignment (MSA) is a constrained combinatorial optimization problem that is generally considered a complex computational problem. In this paper, we first present a binary encoding of MSA and devise a corresponding soft-constrained cost-function that enables a Hamiltonian formulation and implementation of the MSA problem with the variational Quantum Approximate Optimization Algorithm (QAOA). Through theoretical analysis, a bound on the ratio of the number of feasible states to the size of the Hilbert space is determined. Furthermore, we consider a small instance of our QAOA-MSA algorithm in both a quantum simulator and its performance on an actual quantum computer. While the ideal solution to the instance of MSA investigated is shown to be the most probable state sampled for a shallow p<5 quantum circuit in the simulation, the level of noise in current devices is still a formidable challenge for the kind of MSA-QAOA algorithm developed here. In turn, we are not able to distinguish the feasible solutions from other states in the quantum hardware output data at this point. This indicates a need for further investigation into both the strategy utilized for compiling the quantum circuit, but also the possibility of devising a more compact ansatz, as one might achieve through constraint-preserving mixers for QAOA. |
| title | Multi-sequence alignment using the Quantum Approximate Optimization Algorithm |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2308.12103 |