Evaluating NISQ Devices with Quadratic Nonresidues
arXiv:2110.09483
Abstract
We propose a new method for evaluating NISQ devices. This paper has three distinct parts. First, we present a new quantum algorithm that solves a two hundred year old problem of finding quadratic nonresidues (QNR) in polynomial time. We show that QNR is in Exact Quantum Polynomial time, while it is still unknown whether QNR is in P. Second, we present a challenge to create a probability distribution over the quadratic nonresidues. Due to the theoretical complexity gap, a quantum computer can achieve a higher success rate than any known method on a classical computer. A device beating the classical bound indicates quantum advantage or a mathematical breakthrough. Third, we derive a simple circuit for the smallest instance of the quadratic nonresidue test and run it on a variety of currently available NISQ devices. We then present a comparative statistical evaluation of the NISQ devices tested.
arXiv comment20 pages, 14 figures, 2 tables. arXiv admin note: text overlap with arXiv:2106.03991
References in corpus (5)
- Characterizing Quantum Supremacy in Near-Term Devices
- Quantum advantage with shallow circuits
- Experimental demonstration of quantum advantage for one-way communication complexity
- Experimental demonstration of quantum advantage for NP verification with limited information
- Quantum superiority for verifying NP-complete problems with linear optics