Finding Small and Large k-Clique Instances on a Quantum Computer
- URL: http://arxiv.org/abs/2008.12525v1
- Date: Fri, 28 Aug 2020 07:40:44 GMT
- Title: Finding Small and Large k-Clique Instances on a Quantum Computer
- Authors: Sara Ayman Metwalli, Francois Le Gall, Rodney Van Meter
- Abstract summary: We present a gate-based approach to the triangle-finding problem and its NP-hard k-clique generalization.
We examine both constant factors for near-term implementation on a Noisy Intermediate Scale Quantum computer (NISQ) device, and the scaling of the problem to evaluate long-term use of quantum computers.
- Score: 1.1602089225841632
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Algorithms for triangle-finding, the smallest nontrivial instance of the
k-clique problem, have been proposed for quantum computers. Still, those
algorithms assume the use of fixed access time quantum RAM (QRAM). We present a
practical gate-based approach to both the triangle-finding problem and its
NP-hard k-clique generalization. We examine both constant factors for near-term
implementation on a Noisy Intermediate Scale Quantum computer (NISQ) device,
and the scaling of the problem to evaluate long-term use of quantum computers.
We compare the time complexity and circuit practicality of the theoretical
approach and actual implementation. We propose and apply two different
strategies to the k-clique problem, examining the circuit size of Qiskit
implementations. We analyze our implementations by simulating triangle finding
with various error models, observing the effect on damping the amplitude of the
correct answer, and compare to execution on six real IBMQ machines. Finally, we
estimate the date when the methods proposed can run effectively on an actual
device based on IBM's quantum volume exponential growth forecast and the
results of our error analysis.
Related papers
- Realistic Runtime Analysis for Quantum Simplex Computation [0.4407851469168588]
We present a quantum analog for classical runtime analysis when solving real-world instances of important optimization problems.
We show that a practical quantum advantage for realistic problem sizes would require quantum gate operation times that are considerably below current physical limitations.
arXiv Detail & Related papers (2023-11-16T16:11:44Z) - Trainable Variational Quantum-Multiblock ADMM Algorithm for Generation
Scheduling [0.0]
This paper proposes a two-loop quantum solution algorithm for generation scheduling by quantum computing, machine learning, and distributed optimization.
The aim is to facilitate noisy employing near-term quantum machines with a limited number of qubits to solve practical power system problems.
arXiv Detail & Related papers (2023-03-28T21:31:39Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
We provide a complete quantum circuit-level description of the algorithm from problem input to problem output.
We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
arXiv Detail & Related papers (2022-11-22T18:54:48Z) - Demonstration of algorithmic quantum speedup [0.0]
An experimental demonstration of a provable algorithmic quantum speedup has remained elusive.
We implement the single-shot Bernstein-Vazirani algorithm, which solves the problem of identifying a hidden bitstring.
The speedup is observed on only one of the two QCs.
arXiv Detail & Related papers (2022-07-15T17:59:47Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time.
As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware.
We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
arXiv Detail & Related papers (2022-02-17T18:59:20Z) - Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
Two models of quantum computation: CQ_d and QC_d.
CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation.
We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
arXiv Detail & Related papers (2022-01-06T03:10:53Z) - Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance [52.77024349608834]
Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical.
In this paper we present a comparative study of two quantum approaches to computing GED.
arXiv Detail & Related papers (2021-11-19T12:35:26Z) - Multiple Query Optimization using a Hybrid Approach of Classical and
Quantum Computing [1.7077661158850292]
We tackle the multiple query optimization problem (MQO) which is an important NP-hard problem in the area of data-intensive problems.
We propose a novel hybrid classical-quantum algorithm to solve the MQO on a gate-based quantum computer.
Our algorithm shows a qubit efficiency of close to 99% which is almost a factor of 2 higher compared to the state of the art implementation.
arXiv Detail & Related papers (2021-07-22T08:12:49Z) - Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard.
We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware.
The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
arXiv Detail & Related papers (2021-07-08T17:59:55Z) - Large-scale quantum hybrid solution for linear systems of equations [0.0]
We introduce and implement a hybrid quantum algorithm for solving linear systems of equations with exponential speedup.
We solve experimentally a $217$-dimensional problem on superconducting IBMQ devices, a record for linear system solution on quantum computers.
arXiv Detail & Related papers (2020-03-28T11:23:05Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.