More Like this

1. Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints

   https://doi.org/10.22331/q-2023-07-12-1057  

   Patti, Taylor L; Kossaifi, Jean; Anandkumar, Anima; Yelin, Susanne F (July 2023, Quantum)

   Semidefinite programs are optimization methods with a wide array of applications, such as approximating difficult combinatorial problems. One such semidefinite program is the Goemans-Williamson algorithm, a popular integer relaxation technique. We introduce a variational quantum algorithm for the Goemans-Williamson algorithm that uses only $n+1$qubits, a constant number of circuit preparations, and $\text{poly}\left(n\right)$expectation values in order to approximately solve semidefinite programs with up to $N=2^n$variables and $M\sim O\left(N\right)$constraints. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit, a technique known as the Hadamard Test. The Hadamard Test enables us to optimize the objective function by estimating only a single expectation value of the ancilla qubit, rather than separately estimating exponentially many expectation values. Similarly, we illustrate that the semidefinite programming constraints can be effectively enforced by implementing a second Hadamard Test, as well as imposing a polynomial number of Pauli string amplitude constraints. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems, including MaxCut. Our method exceeds the performance of analogous classical methods on a diverse subset of well-studied MaxCut problems from the GSet library. 

   more » « less
2. Faster quantum and classical SDP approximations for quadratic binary optimization

   https://doi.org/10.22331/q-2022-01-20-625  

   G.S L. Brandão, Fernando; Kueng, Richard; Stilck França, Daniel (January 2022, Quantum)

   We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. Such instances include approximating the ground state of spin glasses and MaxCut on Erdös-Rényi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem. 

   more » « less
3. Quantum algorithms and lower bounds for convex optimization

   https://doi.org/10.22331/q-2020-01-13-221  

   Chakrabarti, Shouvanik; Childs, Andrew M.; Li, Tongyang; Wu, Xiaodi (January 2020, Quantum)

   While recent work suggests that quantum computers can speed up the solution of semidefinite programs, little is known about the quantum complexity of more general convex optimization. We present a quantum algorithm that can optimize a convex function over an n -dimensional convex body using O ~ ( n ) queries to oracles that evaluate the objective function and determine membership in the convex body. This represents a quadratic improvement over the best-known classical algorithm. We also study limitations on the power of quantum computers for general convex optimization, showing that it requires Ω ~ ( n ) evaluation queries and Ω ( n ) membership queries. 

   more » « less
4. Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm

   https://doi.org/10.1038/s41534-023-00718-4  

   Lykov, Danylo; Wurtz, Jonathan; Poole, Cody; Saffman, Mark; Noel, Tom; Alexeev, Yuri (December 2023, npj Quantum Information)

   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
5. Demonstration of the rodeo algorithm on a quantum computer

   https://doi.org/10.1140/epja/s10050-024-01373-9  

   Qian, Zhengrong; Watkins, Jacob; Given, Gabriel; Bonitati, Joey; Choi, Kenneth; Lee, Dean (July 2024, The European Physical Journal A)

   The rodeo algorithm is an efficient algorithm for eigenstate preparation and eigenvalue estimation for any observable on a quantum computer. This makes it a promising tool for studying the spectrum and structure of atomic nuclei as well as other fields of quantum many-body physics. The only requirement is that the initial state has sufficient overlap probability with the desired eigenstate. While it is exponentially faster than well-known algorithms such as phase estimation and adiabatic evolution for eigenstate preparation, it has yet to be implemented on an actual quantum device. In this work, we apply the rodeo algorithm to determine the energy levels of a random one-qubit Hamiltonian, resulting in a relative error of 0.08% using mid-circuit measurements on the IBM Q device Casablanca. This surpasses the accuracy of directly-prepared eigenvector expectation values using the same quantum device. We take advantage of the high-accuracy energy determination and use the Hellmann-Feynman theorem to compute eigenvector expectation values for a different random one-qubit observable. For the Hellmann-Feynman calculations, we find a relative error of 0.7%. We conclude by discussing possible future applications of the rodeo algorithm for multi-qubit Hamiltonians. 

   more » « less