Hardware Efficient Quantum Search Algorithm

• URL: http://arxiv.org/abs/2103.14196v1
• Date: Fri, 26 Mar 2021 01:08:50 GMT
• Title: Hardware Efficient Quantum Search Algorithm
• Authors: Ji Liu, Huiyang Zhou
• Abstract summary: 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.
• Score: 17.74233101199813
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum computing has noteworthy speedup over classical computing by taking advantage of quantum parallelism, i.e., the superposition of states. In particular, quantum search is widely used in various computationally hard problems. Grover's search algorithm finds the target element in an unsorted database with quadratic speedup than classical search and has been proved to be optimal in terms of the number of queries to the database. The challenge, however, is that Grover's search algorithm leads to high numbers of quantum gates, which make it infeasible for the Noise-Intermediate-Scale-Quantum (NISQ) computers. In this paper, 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. Our analysis shows that our algorithm has similar oracle complexity to the original Grover's search algorithm while significantly reduces the circuit depth and gate count. The circuit cost reduction leads to a remarkable improvement in the system success rates, paving the way for quantum search on NISQ machines.

Related papers

• Discretized Quantum Exhaustive Search for Variational Quantum Algorithms [0.0]
  Currently available quantum devices have only a limited amount of qubits and a high level of noise, limiting the size of problems that can be solved accurately with those devices. We propose a novel method that can improve variational quantum algorithms -- discretized quantum exhaustive search''
  arXiv  Detail & Related papers  (2024-07-24T22:06:05Z)
• QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum Circuits [82.50620782471485]
  QuantumSEA is an in-time sparse exploration for noise-adaptive quantum circuits. It aims to achieve two key objectives: (1) implicit circuits capacity during training and (2) noise robustness. Our method establishes state-of-the-art results with only half the number of quantum gates and 2x time saving of circuit executions.
  arXiv  Detail & Related papers  (2024-01-10T22:33:00Z)
• Practical Quantum Search by Variational Quantum Eigensolver on Noisy Intermediate-scale Quantum Hardware [0.0]
  We propose a hybrid quantum-classical architecture that replaces quantum iterations with updates from a classical parameterized quantum state. Our approach still maintains usable success probability, while the success probability of Grover search is at the same level as random guessing.
  arXiv  Detail & Related papers  (2023-04-07T17:32:55Z)
• Optimization of probabilistic quantum search algorithm with a priori information [0.21756081703276003]
  Grover's quantum search algorithm is a typical quantum algorithm that proves the superiority of quantum computing over classical computing. We consider a probabilistic Grover search algorithm allowing nonzero probability of failure for a database with a general a priori probability distribution of the elements.
  arXiv  Detail & Related papers  (2023-04-06T04:33:37Z)
• Opening the Black Box Inside Grover's Algorithm [0.0]
  Grover's algorithm is a primary algorithm 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 a linear number of calls to (simulations of) the oracle.
  arXiv  Detail & Related papers  (2023-03-20T17:56:20Z)
• 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)
• 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)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• Quantum search on noisy intermediate-scale quantum devices [7.147209811770232]
  Grover's algorithm is designed without considering the physical resources, such as depth, in the real implementations. We present detailed benchmarks of the five-qubit quantum search algorithm on different quantum processors, including IBMQ, IonQ, and Honeywell quantum devices. Our results show that designing the error-aware quantum search algorithms is possible, which can maximally harness the power of NISQ computers.
  arXiv  Detail & Related papers  (2022-01-31T22:25:58Z)
• 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.