PaperlayerView exact revision on arXiv

Source-linked AI summary

A Quantum Algorithm for Finding the Minimum

Christoph Durr, Peter Hoyer

arXiv:quant-ph/9607014v2quant-phcs.DS

TL;DR

Finding the minimum index in an unsorted table requires a linear number of probes on a classical probabilistic Turing machine. The algorithm repeatedly uses quantum exponential search to find an item smaller than the current threshold and makes that item the new threshold. Running the algorithm c times yields the minimum with probability at least 1 −1/2c.

  • Problem

    Finding the minimum index in an unsorted table requires a linear number of probes on a classical probabilistic Turing machine.

    Source: §1 · p. 1

  • Method

    The algorithm repeatedly uses quantum exponential search to find an item smaller than the current threshold and makes that item the new threshold.

    Source: §1 · p. 1

  • Results

    Running the algorithm c times yields the minimum with probability at least 1 −1/2c.

    Source: §3 · p. 2

  • Takeaways & Limitations

    Quantum exponential search provides a minimum-finding algorithm whose probe complexity is within a constant factor of the optimum.

    Source: §1 · p. 1

    The general-case analysis assumes the same algorithm for nondistinct values, with the key probability relation weakened from equality to an inequality.

    Source: §3 · p. 2

Abstract

from arXiv · show

We give a quantum algorithm to find the index y in a table T of size N such that in time O(c sqrt N), T[y] is minimum with probability at least 1-1/2^c.

1 Introduction

Minimum search requires linear probing classically, while the paper presents a quantum algorithm using O(sqrt N) probes and within a constant factor of optimal.

  • Classical minimum search on an unsorted table requires a linear number of probes.The table contains N items with distinct ordered values, and the goal is to return the index of the minimum.Source: §1 · p. 1
  • The quantum algorithm solves minimum search using O(sqrt N) probes.Source: §1 · p. 1
  • Quantum exponential searching [2], a generalization of Grover’s search [3], is the main subroutine and yields performance within a constant factor of optimal.Source: §1 · p. 1

2 The algorithm

The algorithm repeatedly uses quantum exponential search to replace a threshold index with a smaller item, then analyzes its success through an unbounded version of the process. Its analysis shows how threshold-selection probabilities and search costs yield the stated minimum-finding guarantee and running-time theorem.

Quantum Minimum Searching Algorithm

  • The algorithm uses quantum exponential search to find an item smaller than the current threshold, adopts the resulting index as the new threshold, and repeats until success probability is sufficiently large.It is interrupted when total running time exceeds 22.5; by convention, stage 2(2a) takes lg(N) time steps and each exponential-search iteration takes one time step.Source: §2 · p. 1

Probability analysis

  • In the infinite algorithm, the element of rank r is eventually selected as a threshold with probability 1/r, independently of table size.The analysis considers the minimum among the t items currently smaller than the threshold and proves the probability by induction.Source: §2 · pp. 1–2

Expected running time

  • The expected number of exponential-search iterations for t marked items is at most O(sqrt(N/t)), which supplies the cost bound used in the minimum-search analysis.The bound is attributed to the quantum exponential searching algorithm of [2].Source: §2 · pp. 1–2

Success probability and running time

  • Theorem 1 derives the finite algorithm's success guarantee from the expected-time bound for the infinite algorithm.The proof states that after at most 2m0 iterations, the threshold holds the minimum with the claimed probability, while the theorem also gives a running-time bound.Source: §2 · pp. 1–2

3 Final remarks

Repeating the algorithm c times raises the success probability to at least 1 − 1/2^c, while a single run with an appropriate timeout performs even better. The same lower bound extends to tables with equal values.

3 Final remarks

  • 1 − 1/2^c success probability is achieved by running the algorithm c times and selecting the smallest observed value.The algorithm’s success probability can be amplified through repetition.Source: §3 · p. 2
  • A single run with timeout c2m0 can have better success because it uses information accumulated during earlier steps.Source: §3 · p. 2
  • When table values are not distinct, the same algorithm applies and the theorem’s success-probability lower bound remains valid.The analysis changes only by replacing an equality with an inequality in lemma 1.Source: §3 · p. 2

Acknoledgment

The authors acknowledge discussions and assistance that contributed to raising and developing the minimum-searching problem.

Acknoledgment

  • The authors thank Stephane Boucheron for raising the problem and Richard Cleve and Miklos Santha for helpful discussions.Source: Acknoledgment · p. 2
Loading quant-ph/9607014v2…