Complement Grover's Search Algorithm: An Amplitude Suppression Implementation

• URL: http://arxiv.org/abs/2209.10484v3
• Date: Tue, 1 Aug 2023 11:42:11 GMT
• Title: Complement Grover's Search Algorithm: An Amplitude Suppression Implementation
• Authors: Andrew Vlasic, Salvatore Certo, and Anh Pham
• Abstract summary: Grover's search algorithm was a groundbreaking advancement in quantum algorithms. An extension of Grover's search algorithm is derived where the focus of the query is on the undesirable items. Results are compared against QAOA.
• Score: 0.5352699766206808
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Grover's search algorithm was a groundbreaking advancement in quantum algorithms, displaying a quadratic speed-up of querying for items. Since the creation of this algorithm it has been utilized in various ways, including in preparing specific states for the general circuit. However, as the number of desired items increases so does the gate complexity of the sub-process that conducts the query. To counter this complexity, an extension of Grover's search algorithm is derived where the focus of the query is on the undesirable items in order to suppress the amplitude of the queried items. To display the efficacy the algorithm is implemented as a sub-process into QAOA and applied to a traveling salesman problem. For a basis of comparison, the results are compared against QAOA.

Related papers

• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  We study the real-valued pure exploration problem in the multi-armed bandit (R-CPE-MAB) Existing methods in the R-CPE-MAB can be seen as a special case of the so-called transductive linear bandits. We propose an algorithm named the gap-based exploration (CombGapE) algorithm, whose sample complexity matches the lower bound.
  arXiv  Detail & Related papers  (2023-06-15T15:37:31Z)
• Grover Search Inspired Alternating Operator Ansatz of Quantum Approximate Optimization Algorithm for Search Problems [0.913755431537592]
  We use the mapping between two computation frameworks, Adiabatic Grover Search (AGS) and Adiabatic Quantum Computing (AQC) We then apply Trotterization on the schedule-dependent Hamiltonian of AGS to obtain the values of variational parameters in the Quantum Approximate Optimization Algorithm (QAOA) framework.
  arXiv  Detail & Related papers  (2022-04-21T01:41:36Z)
• Grover search revisited; application to image pattern matching [0.8367938108534343]
  We propose a quantum algorithm that approximately executes the entire Grover database search or pattern matching algorithm. The key idea is to use the recently proposed approximate amplitude encoding method on a shallow quantum circuit.
  arXiv  Detail & Related papers  (2021-08-24T17:30:41Z)
• Determinantal Beam Search [75.84501052642361]
  Beam search is a go-to strategy for decoding neural sequence models. In use-cases that call for multiple solutions, a diverse or representative set is often desired. By posing iterations in beam search as a series of subdeterminant problems, we can turn the algorithm into a diverse subset selection process.
  arXiv  Detail & Related papers  (2021-06-14T13:01:46Z)
• Selection-Expansion: A Unifying Framework for Motion-Planning and Diversity Search Algorithms [69.87173070473717]
  We investigate the properties of two diversity search algorithms, the Novelty Search and the Goal Exploration Process algorithms. The relation to MP algorithms reveals that the smoothness, or lack of smoothness of the mapping between the policy parameter space and the outcome space plays a key role in the search efficiency.
  arXiv  Detail & Related papers  (2021-04-10T13:52:27Z)
• 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)
• 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)
• Number Partitioning with Grover's Algorithm in Central Spin Systems [0.0]
  We propose a Grover search for solutions to a class of NP-complete decision problems known as subset sum problems. Each problem instance is encoded in the couplings of a set of qubits to a central spin or boson, which enables a realization of the oracle without knowledge of the solution.
  arXiv  Detail & Related papers  (2020-09-11T17:31:39Z)
• 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)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  We study the problem of clustering a set of items from binary user feedback. We devise an algorithm with a minimal cluster recovery error rate. For adaptive selection, we develop an algorithm inspired by the derivation of the information-theoretical error lower bounds.
  arXiv  Detail & Related papers  (2019-10-14T09:18:26Z)

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.