Subdivided Phase Oracle for NISQ Search Algorithms

Abstract

Because noisy, intermediate-scale quantum (NISQ) machines accumulate errors quickly, we need new approaches to designing NISQ-aware algorithms and assessing their performance. Algorithms with characteristics that appear less desirable under ideal circumstances, such as lower success probability, may in fact outperform their ideal counterparts on existing hardware. We propose an adaptation of Grover's algorithm, subdividing the phase flip into segments to replace a digital counter and complex phase flip decision logic. We applied this approach to obtaining the best solution of the MAX-CUT problem in sparse graphs, utilizing multi-control, Toffoli-like gates with residual phase shifts. We implemented this algorithm on IBM Q processors and succeeded in solving a 5-node MAX-CUT problem, demonstrating amplitude amplification on four qubits. This approach will be useful for a range of problems, and may shorten the time to reaching quantum advantage.

arXiv comment17 pages, 24 figures

References in corpus (15)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Elementary gates for quantum computation
• Quantum Computing
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Validating quantum computers using randomized model circuits
• Overhead and noise threshold of fault-tolerant quantum error correction
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Minimal Universal Two-qubit Quantum Circuits
• Quantum Counting
• Quantum circuits of T-depth one
• Local and Distributed Quantum Computation
• On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
• Quantum Gates and Circuits
• Five Two-Qubit Gates Are Necessary for Implementing Toffoli Gate

Cited by in corpus (11)

• Implementation of efficient quantum search algorithms on NISQ computers
• Quantum algorithm for Feynman loop integrals
• Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging
• Quantum search on noisy intermediate-scale quantum devices
• Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-phase Toffoli Gates
• Finding solutions to the integer case constraint satisfiability problem using Grover's algorithm
• The Present and Future of Discrete Logarithm Problems on Noisy Quantum Computers
• Amplitude Amplification for Optimization via Subdivided Phase Oracle
• Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Gaussian Amplitude Amplification for Quantum Pathfinding