Is Grover's algorithm suitable for this search problem?

Question

I wonder if we can utilize Grover's algorithm to solve the following search problem.

Leetcode 33. Search in Rotated Sorted Array

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0

Output: true

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3

Output: false

Let's ignore the fact that "the array nums sorted in ascending order" initially and suppose this array is an unstructured list of integers, which satisfied with the problem setting about Grover's algorithm.

So, can I use this Quantum algorithm to solve this problem with $O(\sqrt{N})$ complexity?

How to make an initial uniform superposition with $N$ states, which $N$ is not 2, 4, 8, 16 etc.? For example, I can use 2 qubits and 2 $H$ gates to construct a superposition about $|00\rangle$, $|01\rangle$, $|10\rangle$ and $|11\rangle$, with uniform probabilities $\frac{1}{4}$. But what about a list containing only 3 integers, [0, 2, 3], corresponding $\frac{1}{\sqrt{3}}(|00\rangle + |10\rangle + |11\rangle)$. How to use quantum circuit to express this superposition?

Answer 1

1. Getting arbitrary superpositions can be done without too much difficulty if you have arbitrary single-qubit rotation gates. See here for several answers on how. Though, it might be easier to take Martin Vesely's answer and just expand the array to a power of 2.
2. Generally, to use Grover's algorithm, you have a diffusion operation (the circuit that produces the superposition, described above) and an oracle operation, which can recognize what you are searching for. Grover's algorithm works for a boolean oracle, meaning the result should a yes or no. In the problem you gave, you want to find an index from a target. But this can be done: The circuit you want will take an index as input, retrieve the element of the array at that index (in superposition!), and compare it to the target value, flipping the phase of the state if the result equals the target value.

In this way, Grover's algorithm will return an index $i$ such that $A[i]$ equals the target value. If no such index exists, it will return a random index. So you will need to do one last look-up of index $i$ to check whether the target is there, or not in the array at all.

However: I think Grover's algorithm is a bad choice for this problem. My reasoning is:

1. The array is sorted, except for a pivot! So even though Grover's algorithm can find the target in $O(\sqrt{N})$ queries, a classical binary search should be able to find the pivot and the target in $O(\log N)$ queries. Moreover, if it finds the pivot once, it can keep the pivot.
2. I firmly believe that the actual cost to access $N$ bits of memory in superposition is $O(N)$ (more specifically, $\Theta(N)$). The reason is that the circuit has to have some effect on all $N$ bits of memory, if it's performing an access in superposition, so it needs to apply some gate to every qubit. Given this cost, the total cost of Grover's algorithm is $O(\sqrt{N})$ queries, times $O(N)$ for each query, for $O(N^{3/2})$ total cost. This is more than a classical linear search through the array (if classical memory access is less than $O(N^{1/2})$).

Point #2 is partly personal opinion, though I think it's important to keep in mind that using Grover's algorithm for a search of classical data requires that each oracle call performs a superposition access to all of the memory, however much cost you give to such a procedure.

Answer 2

Any problem that involves searching over stored data is not suited for Grover's algorithm. You would always be better off using a parallel classical machine rather than a quantum computer to solve it.

Sometimes people say there is an advantage, but they are talking about a context where you restrict the classical hardware to have a constant number of CPUs. This is particularly problematic if quantum memory requires error correction driven by classical CPUs, because then the assumptions are implicitly giving $O(n)$ CPUs to the quantum approach but not to the classical approach.

• Serial classical: $O(n^2)$ hardware time ($O(n)$ queries to $O(n)$ bits of RAM handled by $O(1)$ CPUs)
• Parallel classical: $O(n)$ hardware time ($O(1)$ queries to $O(n)$ CPUs)
• Serial quantum: $O(n^{1.5})$ hardware time ($O(\sqrt{n})$ queries to $O(n)$ qubits of quantum ram handled by $O(1)$ quantum processors)
• Parallel quantum: Grover's algorithm is inherently serial, so this just delegates to parallel classical or serial quantum.