An Optimum Algorithm for Quantum Search

• URL: http://arxiv.org/abs/2010.03949v1
• Date: Wed, 7 Oct 2020 09:58:19 GMT
• Title: An Optimum Algorithm for Quantum Search
• Abstract summary: Grover's algorithm can be improved whenever number of 0's and number 1's are not equal. One interesting application is that Dicke state preparation, which in Grover's algorithm is P on average, can be made poly-efficient.
• Score: 4.043829277196036
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper discusses an improvement to Grover's algorithm for searches where target states are Hamming weight eigenstates and search space is not ordered. It is shown that under these conditions search efficiency depends on the smaller number of 0's and 1's, not the total length, of binary string of target state, and that Grover's algorithm can be improved whenever number of 0's and number 1's are not equal. In particular, improvement can be exponential when number of 0's or number of 1's is very small relative to binary string length. One interesting application is that Dicke state preparation, which in Grover's algorithm is P on average, can be made poly-efficient in all cases. For decision making process, this improvement won't improve computation efficiency, but can make implementation much simpler.

Related papers

• Calculating the floor of y**(1/m) [51.56484100374058]
  We present two algorithms based on the Newton-Raphson method to calculate the floor of y** (1/m) for natural integer numbers y>2 and m >1.<n>One could use such an algorithm to establish whether y is an integer power of an integer in number theory problems, even though binary search methods are traditionally considered simpler to implement.
  arXiv  Detail & Related papers  (2026-07-03T16:20:37Z)
• Arbitrary state creation via controlled measurement [49.494595696663524]
  This algorithm creates an arbitrary $n$-qubit pure quantum superposition state with precision of $m$-decimals. The algorithm uses one-qubit rotations, Hadamard transformations and C-NOT operations with multi-qubit controls.
  arXiv  Detail & Related papers  (2025-04-13T07:23:50Z)
• The optimization of exact multi-target quantum search algorithm based on MindSpore [3.633444773654794]
  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%.
  arXiv  Detail & Related papers  (2024-12-24T09:39:59Z)
• Efficient Implementation of a Quantum Search Algorithm for Arbitrary N [0.0]
  This paper presents an enhancement to Grover's search algorithm for instances where $N$ is not a power of 2. By employing an efficient algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, we demonstrate that a considerable reduction in the number of oracle calls (and Grover's iterations) can be achieved in many cases.
  arXiv  Detail & Related papers  (2024-06-19T19:16:40Z)
• A simple quantum algorithm to efficiently prepare sparse states [0.0]
  We show that the gate complexity is linear in the number of non-zero amplitudes in the state and quadratic in the number of qubits. This is competitive with the best known algorithms for sparse state preparation.
  arXiv  Detail & Related papers  (2023-10-30T07:05:15Z)
• 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 Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Pauli String Partitioning Algorithm with the Ising Model for Simultaneous Measurement [0.0]
  We propose an efficient algorithm for partitioning Pauli strings into subgroups, which can be simultaneously measured in a single quantum circuit. Our partitioning algorithm drastically reduces the total number of measurements in a variational quantum eigensolver for a quantum chemistry.
  arXiv  Detail & Related papers  (2022-05-09T01:49:21Z)
• 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)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  We propose a new Hessian inverse free Fully Single Loop Algorithm for bilevel optimization problems. We show that our algorithm converges with the rate of $O(epsilon-2)$.
  arXiv  Detail & Related papers  (2021-12-09T02:27:52Z)
• 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)
• Grover's search algorithm for $n$ qubits with optimal number of iterations [0.0]
  Grover's search algorithm depends on the number of iterations of the composite operation of the oracle followed by Grover's diffusion operation. General scheme for the construction of $n$-qubit Grover's search algorithm with $1 leq M leq N$ target states is presented.
  arXiv  Detail & Related papers  (2020-11-08T18:46:50Z)
• Aligning Partially Overlapping Point Sets: an Inner Approximation Algorithm [80.15123031136564]
  We propose a robust method to align point sets where there is no prior information about the value of the transformation. Our algorithm does not need regularization on transformation, and thus can handle the situation where there is no prior information about the values of the transformations. Experimental results demonstrate the better robustness of the proposed method over state-of-the-art algorithms.
  arXiv  Detail & Related papers  (2020-07-05T15:23:33Z)

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.