Complete 3-Qubit Grover Search on a Programmable Quantum Computer

Abstract

Searching large databases is an important problem with broad applications. The Grover search algorithm provides a powerful method for quantum computers to perform searches with a quadratic speedup in the number of required database queries over classical computers. It is an optimal search algorithm for a quantum computer, and has further applications as a subroutine for other quantum algorithms. Searches with two qubits have been demonstrated on a variety of platforms and proposed for others, but larger search spaces have only been demonstrated on a non-scalable NMR system. Here, we report results for a complete three-qubit Grover search algorithm using the scalable quantum computing technology of trapped atomic ions, with better-than-classical performance. The algorithm is performed for all 8 possible single-result oracles and all 28 possible two-result oracles. Two methods of state marking are used for the oracles: a phase-flip method employed by other experimental demonstrations, and a Boolean method requiring an ancilla qubit that is directly equivalent to the state-marking scheme required to perform a classical search. All quantum solutions are shown to outperform their classical counterparts. We also report the first implementation of a Toffoli-4 gate, which is used along with Toffoli-3 gates to construct the algorithms; these gates have process fidelities of 70.5% and 89.6%, respectively.

11 pages, 10 figures, 2 tables

References in corpus (16)

• Experimental One-Way Quantum Computing
• Demonstration of Two-Qubit Algorithms with a Superconducting Quantum Processor
• Demonstration of a small programmable quantum computer with atomic qubits
• Experimental Comparison of Two Quantum Computing Architectures
• Experimental Demonstration of Blind Quantum Computing
• Manipulation and Detection of a Trapped Yb+ Ion Hyperfine Qubit
• Realization of the quantum Toffoli gate with trapped ions
• On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
• Optimal quantum control of multi-mode couplings between trapped ion qubits for scalable entanglement
• Implementation of Grover's Quantum Search Algorithm in a Scalable System
• Entanglement of Atomic Qubits using an Optical Frequency Comb
• Basic circuit compilation techniques for an ion-trap quantum machine
• Arbitrary-speed quantum gates within large ion crystals through minimum control of laser beams
• Quantum query complexity of some graph problems
• Efficient Grover search with Rydberg blockade
• Correcting detection error in quantum computation and state engineering through data processing

Cited by in corpus (83)

• Trapped-Ion Quantum Computing: Progress and Challenges
• Parallel implementation of high-fidelity multi-qubit gates with neutral atoms
• Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer
• Quantum simulation and computing with Rydberg-interacting qubits
• The Bitter Truth About Quantum Algorithms in the NISQ Era
• Noisy intermediate-scale quantum computers
• Direct randomized benchmarking for multi-qubit devices
• High-fidelity three-qubit iToffoli gate for fixed-frequency superconducting qubits
• Continuous-variable geometric phase and its manipulation for quantum computation in a superconducting circuit
• Two-qubit entangling gates within arbitrarily long chains of trapped ions
• Efficient Implementation of a Quantum Algorithm in a Single Nitrogen Vacancy Center of Diamond
• Low-cost Fredkin gate with auxiliary space
• Scalable algorithm simplification using quantum AND logic
• Depth optimization of quantum search algorithms beyond Grover's algorithm
• Variationally Learning Grover's Quantum Search Algorithm
• $N$-body interactions between trapped ion qubits via spin-dependent squeezing
• Demonstration of three- and four-body interactions between trapped-ion spins
• Use of global interactions in efficient quantum circuit constructions
• Approaching the theoretical limit in quantum gate decomposition
• A programmable three-qubit superconducting processor with all-to-all connectivity
• Implementation of efficient quantum search algorithms on NISQ computers
• Toward convergence of effective field theory simulations on digital quantum computers
• Changing the circuit-depth complexity of measurement-based quantum computation with hypergraph states
• Quantum interference between photons from an atomic ensemble and a remote atomic ion
• Speeding-up the decision making of a learning agent using an ion trap quantum processor
• Number Partitioning with Grover's Algorithm in Central Spin Systems
• Quantum advantage for computations with limited space
• Prospect of using Grover's search in the noisy-intermediate-scale quantum-computer era
• Universal quantum multi-qubit entangling gates with auxiliary spaces
• Comprehensive characterization of three-qubit Grover search algorithm on IBM's 127-qubit superconducting quantum computers
• A brief introduction to quantum algorithms
• Two-dimensional linear trap array for quantum information processing
• Single-qubit universal classifier implemented on an ion-trap quantum device
• A Practical Introduction to Benchmarking and Characterization of Quantum Computers
• Native three-body interaction in superconducting circuits
• Trapped Rydberg ions: a new platform for quantum information processing
• Quantum search on noisy intermediate-scale quantum devices
• Demonstration of Slow Light in a Rubidium Vapour Using Single Photons from a Trapped Ion
• Quantum Simulation Logic, Oracles, and the Quantum Advantage
• Implementation of quantum compression on IBM quantum computers
• A high-fidelity method for a single-step $N$-bit Toffoli gate in trapped ions
• Engineering topological states and quantum-inspired information processing using classical circuits
• Taming quantum systems: A tutorial for using shortcuts-to-adiabaticity, quantum optimal control, and reinforcement learning
• Automatic Generation of an Efficient Less-Than Oracle for Quantum Amplitude Amplification
• Direct Implementation of High-Fidelity Three-Qubit Gates for Superconducting Processor with Tunable Couplers
• Applications of Universal Parity Quantum Computation
• Implementations of more general solid-state (SWAP)${}^{1/m}$ and controlled-(swap)${}^{1/m}$ gates
• Protocols for classically training quantum generative models on probability distributions
• Feasibility of single-shot realizations of conditional three-qubit gates in exchange-coupled qubit arrays with local control
• Signal processing techniques for efficient compilation of controlled rotations in trapped ions
• Limits to Quantum Gate Fidelity from Near-Field Thermal and Vacuum Fluctuations
• Many-body strategies for multi-qubit gates - quantum control through Krawtchouk chain dynamics
• Polarization and Orbital Angular Momentum Encoded Quantum Toffoli Gate Enabled by Diffractive Neural Networks
• Toffoli gate based on a three-body fine-structure-state-changing Förster resonance in Rydberg atoms
• Simulating the quantum Fourier transform, Grover's algorithm, and the quantum counting algorithm with limited entanglement using tensor-networks
• Complexity Bounds on Quantum Search Algorithms in finite-dimensional Networks
• Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
• Rademacher complexity of noisy quantum circuits
• Comparison of Spontaneous Emission in Trapped Ion Multiqubit Gates at High Magnetic Fields
• Exploring Many-body Interactions Through Quantum Fisher Information
• Quantum density peak clustering
• Optimization of probabilistic quantum search algorithm with a priori information
• Characterization, synthesis, and optimization of quantum circuits over multiple-control $\text{Z}$-rotation gates: A systematic study
• Relaxed Peephole Optimization: A Novel Compiler Optimization for Quantum Circuits
• Self-protected adiabatic quantum computation
• Entanglement Dynamics between Ising Spins and a Central Ancilla
• Quantum algorithm for learning secret strings and its experimental demonstration
• An Optimized Quantum Maximum or Minimum Searching Algorithm and its Circuits
• Quantum Computing: an undergraduate approach using Qiskit
• Performance of Uncoded Implementation of Grover's Algorithm on Today's Quantum Processors
• Benchmarking 16-element quantum search algorithms on superconducting quantum processors
• Quantum computing hardware in the cloud: Should a computational chemist care?
• Quantum Ultra-Walks: Walks on a Line with Hierarchical Spatial Heterogeneity
• Invariance of success probability in Grover's quantum search under local noise with memory
• Amplitude Amplification and Estimation using a Floquet system
• Phases and phase transition in Grover's algorithm with systematic noise
• Quantum Search with Prior Knowledge
• High-fidelity multiqubit Rydberg gates via two-photon adiabatic rapid passage
• Three-qubit exact Grover within the blind oracular quantum computation scheme
• Thermal masses and trapped-ion quantum spin models: a self-consistent approach to Yukawa-type interactions in the $\lambda {\varphi }^4$ model
• Two- and three-mode squeezing in a three-qubit entangled system
• Grover's search algorithm for $n$ qubits with optimal number of iterations
• Quantum Circuits Are Just a Phase