Quantum search on noisy intermediate-scale quantum devices

Kun Zhang, Kwangmin Yu, V. E. KorepinarXiv 2022 · DOI · arXiv

TL;DR

Researchers have successfully optimized Grover’s quantum search algorithm for today’s "noisy" quantum hardware by prioritizing circuit depth reduction over theoretical perfection. By benchmarking across IBMQ, IonQ, and Honeywell processors, the team achieved the highest reported success probabilities for a five-qubit search to date, proving that "error-aware" algorithm design is essential for the NISQ era.

What Problem Does This Paper Address?

Grover’s algorithm is a cornerstone of quantum computing, providing a quadratic speedup for searching unstructured databases. However, it was designed for "fault-tolerant" quantum computers—machines that don't exist yet.

Today, we live in the Noisy Intermediate-Scale Quantum (NISQ) era. Current quantum processors have limited "coherence time" and high error rates. The standard implementation of Grover’s algorithm requires a high circuit depth (the number of sequential operations), which often leads to the quantum state collapsing into random noise before a result is reached. The authors address the gap between theoretical algorithm design and the physical constraints of real-world hardware.

Methods

The authors moved beyond the standard "textbook" Grover’s algorithm by implementing several "error-aware" variants:

  1. Depth-Optimized Search: Instead of using a global diffusion operator (which involves all qubits and is very "deep"), they used local diffusion operators. This reduces the number of gates required, trading a slightly lower theoretical success probability for a much higher chance of the hardware actually completing the calculation.
  2. Divide-and-Conquer (Two-Stage) Search: The algorithm is split into two parts. The first stage finds partial bits of the target item, and the second stage finds the rest. This significantly lowers the expected depth needed to find the target.
  3. Hardware-Specific Tweaks: The team used relative-phase Toffoli gates to reduce circuit depth and carefully mapped qubits to minimize "SWAP" gates (which are notoriously error-prone) based on the specific physical connectivity of the processors.

Datasets

While this is a physics/algorithm paper rather than a machine learning paper, the "datasets" are the physical quantum processors used for benchmarking:

  • IBMQ Lagos & Mumbai: Superconducting qubit systems (7 and 27 qubits, respectively) with limited connectivity.
  • IonQ: A trapped-ion system (11 qubits) with all-to-all connectivity.
  • Honeywell System Model H1: A trapped-ion system (12 qubits) with all-to-all connectivity and high quantum volume.

The target state for the search was randomly chosen as $|01011\rangle$ to avoid hardware biases.

Key Insights and Ideas

  • The "Expected Depth" Metric: The authors argue that success probability alone isn't enough to judge a NISQ algorithm. They focus on expected depth—the average total depth required to find the target state across multiple runs.
  • Connectivity is King: Trapped-ion systems (IonQ/Honeywell) outperformed superconducting systems (IBMQ) largely because their "all-to-all" connectivity eliminates the need for extra SWAP gates, keeping the circuits shallow.
  • Grover isn't Optimal for NISQ: Theoretically, Grover’s algorithm is optimal in the number of queries to an oracle. However, in terms of physical depth, the authors show it is often better to use a "sub-optimal" search that is shallower and more robust against noise.
  • Selectivity Matters: The paper uses "Selectivity" to measure how well the algorithm distinguishes the target from noise. A negative selectivity means the algorithm is performing worse than a random guess—a common fate for deep circuits on noisy hardware.

Key Results

  • Record Success: The study achieved a success probability of ~0.49 for a two-iteration, five-qubit Grover search on the Honeywell H1, the highest reported in literature for this scale.
  • Superiority of R3G2M2: A specific depth-optimized circuit (R3G2M2) proved to be the most robust. On IBMQ devices, it was the only circuit that consistently outperformed a classical random guess.
  • Noise Modeling: The authors matched their experimental results with noisy simulations (using a depolarizing channel model), confirming that the Honeywell device operates with an error rate below 0.1% per gate.

Limitations and Future Work

  • Scalability: While these optimizations work for 5 qubits, the authors note that finding the "optimal" divide-and-conquer strategy for 50+ qubits is a classically intractable problem.
  • Oracle Complexity: The study uses a "toy" oracle (a five-qubit controlled phase gate). In real-world applications like AES decryption, the oracle itself would be much deeper and more complex, potentially negating some of these depth savings.
  • Future Directions: The authors suggest exploring how local diffusion operators influence quantum coherence and investigating parallelized versions of the divide-and-conquer strategy.

Summary updated

Abstract

Quantum search algorithm (also known as Grover's algorithm) lays the foundation for many other quantum algorithms. Although it is very simple, its implementation is limited on noisy intermediate-scale quantum (NISQ) processors. Grover's algorithm was designed without considering the physical resources, such as depth, in the real implementations. Therefore, Grover's algorithm can be improved for NISQ devices. In this paper, we demonstrate how to implement quantum search algorithms better on NISQ devices. We present detailed benchmarks of the five-qubit quantum search algorithm on different quantum processors, including IBMQ, IonQ, and Honeywell quantum devices. We report the highest success probability of the five-qubit search algorithm compared to previous works. Our results show that designing the error-aware quantum search algorithms is possible, which can maximally harness the power of NISQ computers.
BibTeX
@misc{zhang2022quantum,
  author = {Kun Zhang and Kwangmin Yu and V. E. Korepin},
  title = {{Quantum search on noisy intermediate-scale quantum devices}},
  year = {2022},
  eprint = {2202.00122},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2202.00122},
}
Figure