Utilizing Novel Quantum Counters for Grover's Algorithm to Solve the Dominating Set Problem

• URL: http://arxiv.org/abs/2312.09388v1
• Date: Thu, 14 Dec 2023 23:00:35 GMT
• Title: Utilizing Novel Quantum Counters for Grover's Algorithm to Solve the Dominating Set Problem
• Authors: Jehn-Ruey Jiang and Qiao-Yi Lin
• Abstract summary: Grover's algorithm is a well-known unstructured quantum search algorithm run on quantum computers. This paper utilizes novel quantum counters with three good properties to construct the oracle of Grover's algorithm.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Grover's algorithm is a well-known unstructured quantum search algorithm run on quantum computers. It constructs an oracle and calls the oracle O($\sqrt N$) times to locate specific data out of N unsorted data. This represents a quadratic speedup compared to the classical unstructured data sequential search algorithm, which requires to call the oracle O(N) times. We are currently in the noisy intermediate-scale quantum (NISQ) era in which quantum computers have a limited number of qubits, short decoherence time, and low gate fidelity. It is thus desirable to design quantum components with three good properties: (i) a reduced number of qubits, (ii) shorter quantum depth, and (iii) fewer gates. This paper utilizes novel quantum counters with the above-mentioned three good properties to construct the oracle of Grover's algorithm to efficiently solve the dominating set problem (DSP), as defined below. For a given graph G=(V, E), a dominating set (DS) D is a subset of the vertex set V, such that every vertex is in D or has an adjacent vertex in D. The DSP is to decide for a given graph G and an integer k whether there exists a DS with size k. Algorithms solving the DSP have many applications. For example, they can be applied to check whether k routers suffice to connect all computers in a computer network. The DSP is an NP-complete problem, indicating that no classical algorithm exists to solve the DSP with polynomial time complexity in the worst case. Therefore, using quantum algorithms, such as Grover's algorithm, to exploit the potent computational capabilities of quantum computers to solve the DSP is highly promising. We execute the whole quantum circuit of Grover's algorithm using novel quantum counters through the IBM Quantum Lab service to validate that the circuit can solve the DSP efficiently and correctly.

Related papers

• Grover's Algorithm Offers No Quantum Advantage [0.0]
  Grover's algorithm is one of the primary algorithms offered as evidence that quantum computers can provide an advantage over classical computers. We construct a quantum inspired algorithm, executable on a classical computer, that performs Grover's task in linear number of call to the oracle. We critically examine the possibility of a practical speedup, a possibility that depends on the nature of the quantum circuit associated with the oracle.
  arXiv  Detail & Related papers  (2023-03-20T17:56:20Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCS aims at index searching and counting in a quantum-classical hybrid system. We implement IQuCS with Qiskit and conduct intensive experiments. Results demonstrate that it reduces qubits consumption by up to 66.2%.
  arXiv  Detail & Related papers  (2022-09-22T21:54:28Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• A Scalable 5,6-Qubit Grover's Quantum Search Algorithm [0.0]
  Grover's quantum search algorithm is one of the well-known applications of quantum computing. In this paper, a scalable Quantum Grover Search algorithm is introduced and implemented using 5-qubit and 6-qubit quantum circuits. The accuracy of the proposed 5-qubit and 6-qubit circuits is benchmarked against the state-of-the-art implementations for 3-qubit and 4-qubit.
  arXiv  Detail & Related papers  (2022-04-30T00:35:54Z)
• Quantum State Preparation with Optimal Circuit Depth: Implementations and Applications [10.436969366019015]
  We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits. We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
  arXiv  Detail & Related papers  (2022-01-27T13:16:30Z)
• 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)
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation [0.0]
  We present a complete analysis of the quantum solvability of the noisy binary linear problem (NBLP) We show that the cost of solving the NBLP can be in the problem size, at the expense of an exponentially increasing logical qubits.
  arXiv  Detail & Related papers  (2021-09-23T07:46:20Z)
• 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)
• Hardware Efficient Quantum Search Algorithm [17.74233101199813]
  We propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. The circuit cost reduction leads to a remarkable improvement in the system success rates.
  arXiv  Detail & Related papers  (2021-03-26T01:08:50Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

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.