More Like this

1. Quantum optimization of maximum independent set using Rydberg atom arrays

   https://doi.org/10.1126/science.abo6587  

   Ebadi, S.; Keesling, A.; Cain, M.; Wang, T. T.; Levine, H.; Bluvstein, D.; Semeghini, G.; Omran, A.; Liu, J.-G.; Samajdar, R.; et al (May 2022, Science)

   Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find the problem hardness is controlled by the solution degeneracy and number of local minima, and experimentally benchmark the quantum algorithm’s performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins. 

   more » « less
2. Near-term distributed quantum computation using mean-field corrections and auxiliary qubits

   https://doi.org/10.1088/2058-9565/ad3f45  

   McClain Gomez, Abigail; Patti, Taylor L.; Anandkumar, Anima; Yelin, Susanne F. (May 2024, Quantum Science and Technology)

   Abstract Distributed quantum computation is often proposed to increase the scalability of quantum hardware, as it reduces cooperative noise and requisite connectivity by sharing quantum information between distant quantum devices. However, such exchange of quantum information itself poses unique engineering challenges, requiring high gate fidelity and costly non-local operations. To mitigate this, we propose near-term distributed quantum computing, focusing on approximate approaches that involve limited information transfer and conservative entanglement production. We first devise an approximate distributed computing scheme for the time evolution of quantum systems split across any combination of classical and quantum devices. Our procedure harnesses mean-field corrections and auxiliary qubits to link two or more devices classically, optimally encoding the auxiliary qubits to both minimize short-time evolution error and extend the approximate scheme’s performance to longer evolution times. We then expand the scheme to include limited quantum information transfer through selective qubit shuffling or teleportation, broadening our method’s applicability and boosting its performance. Finally, we build upon these concepts to produce an approximate circuit-cutting technique for the fragmented pre-training of variational quantum algorithms. To characterize our technique, we introduce a non-linear perturbation theory that discerns the critical role of our mean-field corrections in optimization and may be suitable for analyzing other non-linear quantum techniques. This fragmented pre-training is remarkably successful, reducing algorithmic error by orders of magnitude while requiring fewer iterations. 

   more » « less
3. CAFQA: Clifford Ansatz For Quantum Accuracy

   Gokul Subramanian Ravi, Pranav Gokhale (January 2022, ArXivorg)

   Variational Quantum Algorithms (VQAs) rely upon the iterative optimization of a parameterized unitary circuit with respect to an objective function. Since quantum machines are noisy and expensive resources, it is imperative to choose a VQA's ansatz appropriately and its initial parameters to be close to optimal. This work tackles the problem of finding initial ansatz parameters by proposing CAFQA, a Clifford ansatz for quantum accuracy. The CAFQA ansatz is a hardware-efficient circuit built with only Clifford gates. In this ansatz, the initial parameters for the tunable gates are chosen by searching efficiently through the Clifford parameter space via classical simulation, thereby producing a suitable stabilizer state. The stabilizer states produced are shown to always equal or outperform traditional classical initialization (e.g., Hartree-Fock), and often produce high accuracy estimations prior to quantum exploration. Furthermore, the technique is classically suited since a) Clifford circuits can be exactly simulated classically in polynomial time and b) the discrete Clifford space, while scaling exponentially in the number of qubits, is searched efficiently via Bayesian Optimization. For the Variational Quantum Eigensolver (VQE) task of molecular ground state energy estimation up to 20 qubits, CAFQA's Clifford Ansatz achieves a mean accuracy of near 99%, recovering as much as 99.99% of the correlation energy over Hartree-Fock. Notably, the scalability of the approach allows for preliminary ground state energy estimation of the challenging Chromium dimer with an accuracy greater than Hartree-Fock. With CAFQA's initialization, VQA convergence is accelerated by a factor of 2.5x. In all, this work shows that stabilizer states are an accurate ansatz initialization for VQAs. Furthermore, it highlights the potential for quantum-inspired classical techniques to support VQAs. 

   more » « less
4. Boosting quantum amplitude exponentially in variational quantum algorithms

   https://doi.org/10.1088/2058-9565/acf4ba  

   Kyaw, Thi Ha; Soley, Micheline B; Allen, Brandon; Bergold, Paul; Sun, Chong; Batista, Victor S; Aspuru-Guzik, Alán (October 2023, Quantum Science and Technology)

   Abstract We introduce a family of variational quantum algorithms, which we coin as quantum iterative power algorithms (QIPAs), and demonstrate their capabilities as applied to global-optimization numerical experiments. Specifically, we demonstrate the QIPA based on a double exponential oracle as applied to ground state optimization of theH₂molecule, search for the transmon qubit ground-state, and biprime factorization. Our results indicate that QIPA outperforms quantum imaginary time evolution (QITE) and requires a polynomial number of queries to reach convergence even with exponentially small overlap between an initial quantum state and the final desired quantum state, under some circumstances. We analytically show that there exists an exponential amplitude amplification at every step of the variational quantum algorithm, provided the initial wavefunction has non-vanishing probability with the desired state and that the unique maximum of the oracle is given by ${\lambda }_1>0$, while all other values are given by the same value $0<{\lambda }_2<{\lambda }_1$(hereλcan be taken as eigenvalues of the problem Hamiltonian). The generality of the global-optimization method presented here invites further application to other problems that currently have not been explored with QITE-based near-term quantum computing algorithms. Such approaches could facilitate identification of reaction pathways and transition states in chemical physics, as well as optimization in a broad range of machine learning applications. The method also provides a general framework for adaptation of a class of classical optimization algorithms to quantum computers to further broaden the range of algorithms amenable to implementation on current noisy intermediate-scale quantum computers. 

   more » « less
5. Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints

   Wang, Iria W; Brown, Robin; Patti, Taylor L; Anandkumar, Anima; Pavone, Marco; Yelin, Sussane F (August 2024, arXivorg)

   Quantum computation shows promise for addressing numerous classically intractable problems, such as optimization tasks. Many optimization problems are NP-hard, meaning that they scale exponentially with problem size and thus cannot be addressed at scale by traditional computing paradigms. The recently proposed quantum algorithm arXiv:2206.14999 addresses this challenge for some NP-hard problems, and is based on classical semidefinite programming (SDP). In this manuscript, we generalize the SDP-inspired quantum algorithm to sum-of-squares programming, which targets a broader problem set. Our proposed algorithm addresses degree- polynomial optimization problems with variables (which are representative of many NP-hard problems) using qubits, quantum measurements, and classical calculations. We apply the proposed algorithm to the prototypical Max-SAT problem and compare its performance against classical sum-of-squares, state-of-the-art heuristic solvers, and random guessing. Simulations show that the performance of our algorithm surpasses that of classical sum-of-squares after rounding. Our results further demonstrate that our algorithm is suitable for large problems and approximates the best known classical heuristics, while also providing a more generalizable approach compared to problem-specific heuristics. 

   more » « less