Finding Small and Large k-Clique Instances on a Quantum Computer

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.

References in corpus (19)

• Quantum random access memory
• Tight bounds on quantum searching
• Validating quantum computers using randomized model circuits
• Multipartite entanglement and high precision metrology
• Procedure for systematically tuning up crosstalk in the cross resonance gate
• Overhead and noise threshold of fault-tolerant quantum error correction
• Experimental realization of Dicke states of up to six qubits for multiparty quantum networking
• Fault-Tolerant Logical Gates in the IBM Quantum Experience
• Efficient quantum algorithms for $GHZ$ and $W$ states, and implementation on the IBM quantum computer
• Deterministic Preparation of Dicke States
• Automated distribution of quantum circuits via hypergraph partitioning
• Quantum circuit optimizations for NISQ architectures
• Extracting Success from IBM's 20-Qubit Machines Using Error-Aware Compilation
• A necessary and sufficient condition to play games in quantum mechanical settings
• Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments
• Circuit Transformations for Quantum Architectures
• Decoherence and dephasing in spin-based solid state quantum computers
• Quantum algorithms for subset finding
• Finding cliques by quantum adiabatic evolution

Cited by in corpus (8)

• NISQ Computers: A Path to Quantum Supremacy
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis
• A Tool For Debugging Quantum Circuits
• Circuit Design for Clique Problem and Its Implementation on Quantum Computer
• Lower bounds for adiabatic quantum algorithms by quantum speed limits
• Topological Signal Processing on Quantum Computers for Higher-Order Network Analysis
• Robust Quantum Circuit for Clique Problem with Intermediate Qudits
• Quantum HodgeRank: Topology-Based Rank Aggregation on Quantum Computers