An official website of the United States government
We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers Gurobi and MQLib to solve the MaxCut problem on 3-regular graphs. We identify the minimum noiseless sampling frequency and depthprequired for a quantum device to outperform classical algorithms. There is potential for quantum advantage on hundreds of qubits and moderate depth with a sampling frequency of 10 kHz. We observe, however, that classical heuristic solvers are capable of producing high-quality approximate solutions in linear time complexity. In order to match this quality for large graph sizesN, a quantum device must support depthp > 11. Additionally, multi-shot QAOA is not efficient on large graphs, indicating that QAOAp ≤ 11 does not scale withN. These results limit achieving quantum advantage for QAOA MaxCut on 3-regular graphs. Other problems, such as different graphs, weighted MaxCut, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.
more »
« less
Digital Tavis-Cummings Simulation on Superconducting Quantum Hardware with Error Mitigation
We explore digital quantum simulation of the dynamics ofNemitters coupled to an optical cavity (Tavis-Cummings model) on superconducting quantum hardware and successfully mitigate errors using randomized compiling and noiseless output extrapolation methods.
more »
« less
- Award ID(s):
- 2047564
- PAR ID:
- 10481322
- Publisher / Repository:
- Optica Publishing Group
- Date Published:
- ISBN:
- 978-1-957171-27-2
- Page Range / eLocation ID:
- QM2A.3
- Format(s):
- Medium: X
- Location:
- Denver, Colorado
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Numerous quantum algorithms require the use of quantum error correction to overcome the intrinsic unreliability of physical qubits. However, quantum error correction imposes a unique performance bottleneck, known asT-complexity, that can make an implementation of an algorithm as a quantum program run more slowly than on idealized hardware. In this work, we identify that programming abstractions for control flow, such as the quantum if-statement, can introduce polynomial increases in theT-complexity of a program. If not mitigated, this slowdown can diminish the computational advantage of a quantum algorithm. To enable reasoning about the costs of control flow, we present a cost model that a developer can use to accurately analyze theT-complexity of a program under quantum error correction and pinpoint the sources of slowdown. To enable the mitigation of these costs, we present a set of program-level optimizations that a developer can use to rewrite a program to reduce itsT-complexity, predict theT-complexity of the optimized program using the cost model, and then compile it to an efficient circuit via a straightforward strategy. We implement the program-level optimizations in Spire, an extension of the Tower quantum compiler. Using a set of 11 benchmark programs that use control flow, we empirically show that the cost model is accurate, and that Spire’s optimizations recover programs that are asymptotically efficient, meaning their runtimeT-complexity under error correction is equal to their time complexity on idealized hardware. Our results show that optimizing a program before it is compiled to a circuit can yield better results than compiling the program to an inefficient circuit and then invoking a quantum circuit optimizer found in prior work. For our benchmarks, only 2 of 8 tested quantum circuit optimizers recover circuits with asymptotically efficientT-complexity. Compared to these 2 optimizers, Spire uses 54×–2400× less compile time.more » « less
-
Abstract Tavis-Cummings (TC) cavity quantum electrodynamical effects, describing the interaction ofNatoms with an optical resonator, are at the core of atomic, optical and solid state physics. The full numerical simulation of TC dynamics scales exponentially with the number of atoms. By restricting the open quantum system to a single excitation, typical of experimental realizations in quantum optics, we analytically solve the TC model with an arbitrary number of atoms with linear complexity. This solution allows us to devise the Quantum Mapping Algorithm of Resonator Interaction withNAtoms (Q-MARINA), an intuitive TC mapping to a quantum circuit with linear space and time scaling, whoseN+1 qubits represent atoms and a lossy cavity, while the dynamics is encoded through 2Nentangling gates. Finally, we benchmark the robustness of the algorithm on a quantum simulator and superconducting quantum processors against the quantum master equation solution on a classical computer.more » « less
-
Abstract We present a systematic study of quantum receivers and modulation methods enabling resource efficient quantum-enhanced optical communication. We introduce quantum-inspired modulation schemes that theoretically yield a better resource efficiency than legacy protocols. Experimentally, we demonstrate below the shot-noise limit symbol error rates forM ≤ 16 legacy and quantum-inspired communication alphabets using software-configurable optical communication time-resolving quantum receiver testbed. Further, we experimentally verify that our quantum-inspired modulation schemes boost the accuracy of practical quantum measurements and significantly optimize the combined use of energy and bandwidth for communication alphabets that are longer thanM = 4 symbols.more » « less
-
Abstract We definelazinessto describe a large suppression of variational parameter updates for neural networks, classical or quantum. In the quantum case, the suppression is exponential in the number of qubits for randomized variational quantum circuits. We discuss the difference between laziness andbarren plateauin quantum machine learning created by quantum physicists in McCleanet al(2018Nat. Commun.91–6) for the flatness of the loss function landscape during gradient descent. We address a novel theoretical understanding of those two phenomena in light of the theory of neural tangent kernels. For noiseless quantum circuits, without the measurement noise, the loss function landscape is complicated in the overparametrized regime with a large number of trainable variational angles. Instead, around a random starting point in optimization, there are large numbers of local minima that are good enough and could minimize the mean square loss function, where we still have quantum laziness, but we do not have barren plateaus. However, the complicated landscape is not visible within a limited number of iterations, and low precision in quantum control and quantum sensing. Moreover, we look at the effect of noises during optimization by assuming intuitive noise models, and show that variational quantum algorithms are noise-resilient in the overparametrization regime. Our work precisely reformulates the quantum barren plateau statement towards a precision statement and justifies the statement in certain noise models, injects new hope toward near-term variational quantum algorithms, and provides theoretical connections toward classical machine learning. Our paper provides conceptual perspectives about quantum barren plateaus, together with discussions about the gradient descent dynamics in Liuet al(2023Phys. Rev. Lett.130150601).more » « less
