Quantum partial search for uneven distribution of multiple target items

DOI10.1007/S11128-018-1907-9MaRDI QIDQ1993754zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 5 November 2018

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.08230

zbMATH Keywords

optimizationquantum algorithmapproximate searchGrover searchdatabase searchmultiple targets

Mathematics Subject Classification ID

Searching and sorting (68P10) Quantum computation (81P68)

Abstract: Quantum partial search algorithm is approximate search. It aims to find a target block (which has the target items). It runs a little faster than full Grover search. In this paper, we consider quantum partial search algorithm for multiple target items unevenly distributed in database (target blocks have different number of target items). The algorithm we describe can locate one of the target blocks. Efficiency of the algorithm is measured by number of queries to the oracle. We optimize the algorithm in order to improve efficiency. By perturbation method, we find that the algorithm runs the fastest when target items are evenly distributed in database.

Recommendations

• Quantum partial search of a database with several target items
• Simple algorithm for partial quantum search
• Optimization of partial search
• Quest for fast partial search algorithm
• Hierarchical quantum search

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• A review on quantum search algorithms
• Coins make quantum walks faster
• Group Theoretical Formulation of a Quantum Partial Search Algorithm
• HIERARCHICAL QUANTUM SEARCH
• Nested quantum search and NP-hard problems
• Optimization of partial search
• Quantum partial search of a database with several target items
• Quantum search algorithms
• Quantum speed-up for unsupervised learning
• Quest for fast partial search algorithm
• Simple algorithm for partial quantum search
• Strengths and Weaknesses of Quantum Computing
• Sure success partial search

Cited in

(6)

• Quantum partial search algorithm with smaller oracles for multiple target items
• Deterministic quantum partial search for target states with proportion 1/16
• Quantum walk search on a two-dimensional grid with extra edges
• Performance analysis of the hardware-efficient quantum search algorithm
• Quantum search on Hanoi network
• Quantum partial search of a database with several target items

This page was built for publication: Quantum partial search for uneven distribution of multiple target items

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1993754)