The optimization of exact multi-target quantum search algorithm based on MindSpore

• URL: http://arxiv.org/abs/2412.18306v2
• Date: Thu, 09 Jan 2025 11:43:07 GMT
• Title: The optimization of exact multi-target quantum search algorithm based on MindSpore
• Authors: Shijin Zhong, Wei Li, Guangzhen Dai, Daohua Wu,
• Abstract summary: We present an optimized exact multi-target search algorithm based on the modified Grover's algorithm. The proposed algorithm can reduce the quantum gate count by at least 21.1% and the depth of the quantum circuit by at least 11.4%.
• Score: 3.633444773654794
• License:
• Abstract: Grover's search algorithm has attracted great attention due to its quadratic speedup over classical algorithms in unsorted database search problems. However, Grover's algorithm is inefficient in multi-target search problems, except in the case of 1/4 of the data in the database satisfying the search conditions. Long presented a modified version of Grover's search algorithm by introducing a phase-matching condition that can search for the target state with a zero theoretical failure rate. In this work, we present an optimized exact multi-target search algorithm based on the modified Grover's algorithm by transforming the canonical diffusion operator to a more efficient diffusion operator, which can solve the multi-target search problem with a 100% success rate while requiring fewer gate counts and shallower circuit depth. After that, the optimized multi-target algorithm for four different items, including 2-qubit with 2 targets, 5-qubit with 2 targets, 5-qubit with 4 targets, and 6-qubit with 3 targets, are implemented on MindSpore framework. The experimental results show that, compared with Grover's algorithm and the modified Grover's algorithm, the proposed algorithm can reduce the quantum gate count by at least 21.1% and the depth of the quantum circuit by at least 11.4% and maintain a 100% success probability. Our code are available at https://github.com/mindsporelab/models/tree/master/research/arxiv_papers/GROVER-OP. Thanks for the support provided by MindSpore Community.

Related papers

• Distributed exact multi-objective quantum search algorithm [9.09986332387569]
  Grover's algorithm has quadratic acceleration in multi-objection search. Iterated operator in Grover's algorithm is a key element and plays an important role in amplitude amplification.
  arXiv  Detail & Related papers  (2024-09-06T06:16:53Z)
• Near-deterministic quantum search algorithm without phase design [10.754825115553086]
  Grover's algorithm can find the target state with certainty only if searching one out of four. deterministic search algorithm is also designed when searching one out of eight, sixteen, and thirty-two.
  arXiv  Detail & Related papers  (2024-07-15T14:20:47Z)
• Distributed Exact Generalized Grover's Algorithm [9.675088142486729]
  We propose a distributed Exactized Grover's Algorithm (DEGGA) to solve a generalized search problem. Our algorithm ensures accuracy, with a theoretical probability of identifying the target states at $100%$. Our method requires a total of $n$ qubits, eliminating the need for auxiliary qubits.
  arXiv  Detail & Related papers  (2024-05-11T09:17:11Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Deterministic Grover search with a restricted oracle [2.976027966501599]
  Grover's quantum search algorithm provides a quadratic quantum advantage over classical algorithms. We present a modified version to return the correct result with certainty without having user control over the quantum search oracle.
  arXiv  Detail & Related papers  (2022-01-01T02:04:11Z)
• OMPQ: Orthogonal Mixed Precision Quantization [64.59700856607017]
  Mixed precision quantization takes advantage of hardware's multiple bit-width arithmetic operations to unleash the full potential of network quantization. We propose to optimize a proxy metric, the concept of networkity, which is highly correlated with the loss of the integer programming. This approach reduces the search time and required data amount by orders of magnitude, with little compromise on quantization accuracy.
  arXiv  Detail & Related papers  (2021-09-16T10:59:33Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Quantum Search with Prior Knowledge [15.384459603233978]
  We propose a new generalization of Grover's search algorithm which performs better than the standard Grover algorithm in average under this setting. We prove that our new algorithm achieves the optimal expected success probability of finding the solution if the number of queries is fixed.
  arXiv  Detail & Related papers  (2020-09-18T09:50:33Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58:26Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

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.