Phases and phase transition in Grover's algorithm with systematic noise

Abstract

While limitations on quantum computation by Markovian environmental noise are well-understood in generality, their behavior for different quantum circuits and noise realizations can be less universal. Here we consider a canonical quantum algorithm - Grover's algorithm for unordered search on $L$ qubits - in the presence of systematic noise. This allows us to write the behavior as a random Floquet unitary, which we show is well-characterized by random matrix theory (RMT). The RMT analysis enables analytical predictions for phases and phase transitions of the many-body dynamics. We find two separate transitions. At moderate disorder ${\delta }_{c,\mathrm{gap}}\sim L^{-1}$, there is a ergodicity breaking transition such that a finite-dimensional manifold remains non-ergodic for $\delta <{\delta }_{c,\mathrm{gap}}$. Computational power is lost at a much smaller disorder, ${\delta }_{c,\mathrm{comp}}\sim L^{-1/2}{2}^{-L/2}$. We comment on relevance to non-systematic noise in realistic quantum computers, including cold atom, trapped ion, and superconducting platforms.

14 pages, 11 figures

References in corpus (19)

• Quantum Computing in the NISQ era and beyond
• Localization of interacting fermions at high temperature
• Noisy intermediate-scale quantum (NISQ) algorithms
• Universal High-Frequency Behavior of Periodically Driven Systems: from Dynamical Stabilization to Floquet Engineering
• Many-body localization edge in the random-field Heisenberg chain
• The distribution of the ratio of consecutive level spacings in random matrix ensembles
• Floquet Engineering of Quantum Materials
• Absolute Stability and Spatiotemporal Long-Range Order in Floquet systems
• Complete 3-Qubit Grover Search on a Programmable Quantum Computer
• The fate of a discrete time crystal in an open system
• Instability of many-body localized systems as a phase transition in a nonstandard thermodynamic limit
• Linear-Depth Quantum Circuits for n-qubit Toffoli gates with no Ancilla
• Linear-depth quantum circuits for multiqubit controlled gates
• Realistic many-body quantum systems vs full random matrices: static and dynamical properties
• Implementation of efficient quantum search algorithms on NISQ computers
• Noise effect on Grover algorithm
• Number Partitioning with Grover's Algorithm in Central Spin Systems
• Quantum search on noisy intermediate-scale quantum devices
• Quantifying quantum chaos through microcanonical distributions of entanglement

Cited by in corpus (1)

• Quantum algorithm for unstructured search of ranked targets