The DOI matches its Crossref record; 122 of the 122 references it cites were found in a registry or an index.
Warm-starting quantum optimization
Open accessAbstract
There is an increasing interest in quantum algorithms for problems of integer programming and combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best performance ratios available classically in polynomial time. Here, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. In particular, this allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“Concerning the former, a preconditioning of the quantum algorithm for VQAs is provided by warm-starting with classical solvers for relaxed CO problems [42], e.g., an SDP solver [137].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [42]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
Einstein, A., Podolsky, B., & Rosen, N. (1935) · Physical Review · doi:10.1103/physrev.47.777 · Cited by 16,654
Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., & Lloyd, S. (2017) · Nature · doi:10.1038/nature23474 · Cited by 4,779
Markowitz, H. M. (1952) · The Journal of Finance · doi:10.2307/2975974 · Cited by 4,606
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
A second course in stochastic processes
Karlin, S., & Taylor, H. E. (1981) · Cited by 2,770
Supervised learning with quantum-enhanced feature spaces
Havlíček, V., Córcoles, A. D., Temme, K., Harrow, A. W., Kandala, A., Chow, J. M., & Gambetta, J. M. (2019) · Nature · doi:10.1038/s41586-019-0980-2 · Cited by 2,572
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512
Global Optimization with Polynomials and the Problem of Moments
Lasserre, J. B. (2001) · SIAM Journal on Optimization · doi:10.1137/s1052623400366802 · Cited by 2,412
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · Cited by 2,374
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
Quantum annealing with manufactured spins
Johnson, M. W., Amin, M. H. S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A. J., Johansson, J., Bunyk, P., et al. (2011) · Nature · doi:10.1038/nature10012 · Cited by 1,891
Quantum generalizations of Bell's inequality
Cirel'son, B. S. (1980) · Letters in Mathematical Physics · doi:10.1007/bf00417500 · Cited by 1,788
P-Complete Approximation Problems
Sahni, S. K., & Gonzalez, T. F. (1976) · Journal of the ACM · doi:10.1145/321958.321975 · Cited by 1,725
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · doi:10.1017/cbo9780511804090 · Cited by 1,690
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470
Qiskit: An Open-source Framework for Quantum Computing
Aleksandrowicz, G., Alexander, T., Barkoutsos, P. K., Bello, L., Ben-Haim, Y., Bucher, D., Cabrera-Hernández, F. J., Carballo-Franquis, J., Chen, A., Chen, C.-F., et al. (2019) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.2562110 · Cited by 1,454
Proof verification and the hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998) · Journal of the ACM · doi:10.1145/278298.278306 · Cited by 1,449
Qiskit: An Open-source Framework for Quantum Computing
Aleksandrowicz, G., Alexander, T., Barkoutsos, P. K., et al. (2019) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.2562111 · Cited by 1,314
Complexity and real computation
Blum, L. (1998) · Choice Reviews Online · doi:10.5860/choice.35-6275c · Cited by 1,266
Probabilistic checking of proofs
Arora, S., & Safra, M. (1998) · Journal of the ACM · doi:10.1145/273865.273901 · Cited by 1,158
Randomized rounding: A technique for provably good algorithms and algorithmic proofs
Raghavan, P., & Tompson, C. D. (1987) · COMBINATORICA · doi:10.1007/bf02579324 · Cited by 1,021
Error mitigation extends the computational reach of a noisy quantum processor
Kandala, A., Temme, K., Corcoles, A. D., Mezzacapo, A., Chow, J. M., & Gambetta, J. (2019) · Nature · doi:10.1038/s41586-019-1040-7 · Cited by 947
Zhou, L., Wang, S.-T., Choi, S., Pichler, H., & Lukin, M. D. (2020) · Physical Review X · doi:10.1103/physrevx.10.021067 · Cited by 913
Complexity and Real Computation
Blum, L., Felipe Cucker, B., Shub, M., & Smale, S. (1998) · Springer eBooks · doi:10.1007/978-1-4612-0701-6 · Cited by 869
On the power of unique 2-prover 1-round games
Khot, S. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.510017 · Cited by 825
Quantum computing for finance: Overview and prospects
Orús, R., Mugel, S., & Lizaso, E. (2019) · Reviews in Physics · doi:10.1016/j.revip.2019.100028 · Cited by 792
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R. (2019) · Algorithms · doi:10.3390/a12020034 · Cited by 772
Quantum optimization using variational algorithms on near-term quantum devices
Moll, N., Barkoutsos, P., Bishop, L. S., Chow, J. M., Cross, A., Egger, D. J., Filipp, S., Fuhrer, A., Gambetta, J. M., Ganzhorn, M., et al. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aab822 · Cited by 744
Self-citationOptimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
Khot, S., Kindler, G., Mossel, E., & O’Donnell, R. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447372 · Cited by 592
Computational Complexity: ADVANCED TOPICS
Arora, S., & Barak, B. (2009) · Cited by 578
Quantum approximate optimization of non-planar graph problems on a planar superconducting processor
Harrigan, M. P., Sung, K. J., Neeley, M., Satzinger, K. J., Arute, F., Arya, K., Atalaya, J., Bardin, J. C., Barends, R., Boixo, S., et al. (2021) · Nature Physics · doi:10.1038/s41567-020-01105-y · Cited by 564
Boolean Methods in Operations Research and Related Areas
Hammer, P. L., & Rudeanu, S. (1968) · Ökonometrie und Unternehmensforschung · doi:10.1007/978-3-642-85823-9 · Cited by 529
The PCP theorem by gap amplification
Dinur, I. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132553 · Cited by 506
Digitized adiabatic quantum computing with a superconducting circuit
Barends, R., Shabani, A., Lamata, L., Kelly, J., Mezzacapo, A., Heras, U. L., Babbush, R., Fowler, A. G., Campbell, B., Chen, Y., et al. (2016) · Nature · doi:10.1038/nature17658 · Cited by 474
Quantum Computing for Finance: State-of-the-Art and Future Prospects
Egger, D. J., Gambella, C., Marecek, J., McFaddin, S., Mevissen, M., Raymond, R., Simonetto, A., Woerner, S., & Yndurain, E. (2020) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2020.3030314 · Cited by 466
Self-citationOptimal algorithms and inapproximability results for every CSP?
Raghavendra, P. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374414 · Cited by 390
Woerner, S., & Egger, D. J. (2019) · npj Quantum Information · doi:10.1038/s41534-019-0130-6 · Cited by 364
Self-citationBarkoutsos, P. K., Gonthier, J. F., Sokolov, I., Moll, N., Salis, G., Fuhrer, A., Ganzhorn, M., Egger, D. J., Troyer, M., Mezzacapo, A., et al. (2018) · Physical Review A · doi:10.1103/physreva.98.022322 · Cited by 363 · cited 1×
“For example, the particle-hole representation for VQE can be seen as a form of warm-start [89].”
BackgroundSelf-citationQuantum approximate optimization algorithm for MaxCut: A fermionic view
Wang, Z., Hadfield, S., Jiang, Z., & Rieffel, E. G. (2018) · Physical Review A · doi:10.1103/physreva.97.022304 · Cited by 353
Option Pricing using Quantum Computers
Stamatopoulos, N., Egger, D. J., Sun, Y., Zoufal, C., Iten, R., Shen, N., & Woerner, S. (2020) · Quantum · doi:10.22331/q-2020-07-06-291 · Cited by 337
Self-citationHandbook on Semidefinite, Conic and Polynomial Optimization
Lasserre, J.-B., & Miguel, A. (2011) · International series in management science/operations research/International series in operations research & management science · doi:10.1007/978-1-4614-0769-0 · Cited by 325
Zhu, L., Tang, H. L., Barron, G. S., Calderon-Vargas, F. A., Mayhall, N. J., Barnes, E., & Economou, S. E. (2022) · Physical Review Research · doi:10.1103/physrevresearch.4.033029 · Cited by 293
Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
Lasserre, J. B. (2006) · SIAM Journal on Optimization · doi:10.1137/05064504x · Cited by 292
Exploring Entanglement and Optimization within the Hamiltonian Variational Ansatz
Wiersema, R., Zhou, C., de Sereville, Y., Carrasquilla, J., Kim, Y. B., & Yuen, H. (2020) · PRX Quantum · doi:10.1103/prxquantum.1.020319 · Cited by 289
Rigorous location of phase transitions in hard optimization problems
Achlioptas, D., Naor, A., & Peres, Y. (2005) · Nature · doi:10.1038/nature03602 · Cited by 284
Obstacles to Variational Quantum Optimization from Symmetry Protection
Bravyi, S., Kliesch, A., Koenig, R., & Tang, E. (2020) · Physical Review Letters · doi:10.1103/physrevlett.125.260505 · Cited by 278
Improving Variational Quantum Optimization using CVaR
Barkoutsos, P. K., Nannicini, G., Robert, A., Tavernelli, I., & Woerner, S. (2020) · Quantum · doi:10.22331/q-2020-04-20-256 · Cited by 263
Self-citationQuantum computational finance: Monte Carlo pricing of financial derivatives
Rebentrost, P., Gupt, B., & Bromley, T. R. (2018) · Physical Review A · doi:10.1103/physreva.98.022321 · Cited by 262
Optimizing Variational Quantum Algorithms Using Pontryagin’s Minimum Principle
Yang, Z.-C., Rahmani, A., Shabani, A., Neven, H., & Chamon, C. (2017) · Physical Review X · doi:10.1103/physrevx.7.021027 · Cited by 210
Maximizing Quadratic Programs: Extending Grothendieck's Inequality
Charikar, M., & Wirth, A. I. (2004) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.39 · Cited by 204
A recipe for semidefinite relaxation for (0,1)-quadratic programming
Poljak, S., Rendl, F., & Wolkowicz, H. (1995) · Journal of Global Optimization · doi:10.1007/bf01100205 · Cited by 200
Checking local optimality in constrained quadratic programming is NP-hard
Pardalos, P. M., & Schnitger, G. (1988) · Operations Research Letters · doi:10.1016/0167-6377(88)90049-1 · Cited by 193
XY mixers: Analytical and numerical results for the quantum alternating operator ansatz
Wang, Z., Rubin, N. C., Dominy, J. M., & Rieffel, E. G. (2020) · Physical Review A · doi:10.1103/physreva.101.012320 · Cited by 190
Qiskit pulse: programming quantum computers through the cloud with pulses
Alexander, T., Kanazawa, N., Egger, D. J., Capelluto, L., Wood, C. J., Javadi-Abhari, A., & McKay, D. C. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/aba404 · Cited by 183
Self-citationCredit Risk Analysis Using Quantum Computers
Egger, D. J., Gutiérrez, R. G., Mestre, J. C., & Woerner, S. (2020) · IEEE Transactions on Computers · doi:10.1109/tc.2020.3038063 · Cited by 174
Self-citationPerformance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
Crooks, G. E. (2018) · arXiv · doi:10.48550/arxiv.1811.08419 · Cited by 158
Gate-Efficient Simulation of Molecular Eigenstates on a Quantum Computer
Ganzhorn, M., Egger, D. J., Barkoutsos, P., Ollitrault, P. J., Salis, G., Moll, N., Roth, M., Fuhrer, A., Mueller, P., Woerner, S., et al. (2019) · Physical Review Applied · doi:10.1103/physrevapplied.11.044092 · Cited by 154
Self-citationReachability Deficits in Quantum Approximate Optimization
Akshay, V., Philathong, H., Morales, M. E. S., & Biamonte, J. D. (2020) · Physical Review Letters · doi:10.1103/physrevlett.124.090504 · Cited by 151
Classical and quantum bounded depth approximation algorithms
Hastings, M. B. (2019) · Quantum Information and Computation · doi:10.26421/qic19.13-14-3 · Cited by 144
A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1412.6062 · Cited by 131
What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO
Dunning, I., Gupta, S., & Silberholz, J. (2018) · INFORMS Journal on Computing · doi:10.1287/ijoc.2017.0798 · Cited by 128
Benchmarking the quantum approximate optimization algorithm
Willsch, M., Willsch, D., Jin, F., De Raedt, H., & Michielsen, K. (2020) · Quantum Information Processing · doi:10.1007/s11128-020-02692-8 · Cited by 128
Near-optimal algorithms for unique games
Charikar, M., Makarychev, K., & Makarychev, Y. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132547 · Cited by 124
Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
Bartschi, A., & Eidenbenz, S. (2020) · 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) · doi:10.1109/qce49297.2020.00020 · Cited by 122
Rounding Semidefinite Programming Hierarchies via Global Correlation
Barak, B., Raghavendra, P., & Steurer, D. (2011) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.95 · Cited by 119
Learning to Optimize Variational Quantum Circuits to Solve Combinatorial Problems
Khairy, S., Shaydulin, R., Cincio, L., Alexeev, Y., & Balaprakash, P. (2020) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v34i03.5616 · Cited by 117
Scalable Semidefinite Programming
Yurtsever, A., Tropp, J. A., Fercoq, O., Udell, M. R., & Cevher, V. (2021) · SIAM Journal on Mathematics of Data Science · doi:10.1137/19m1305045 · Cited by 111
Multistart Methods for Quantum Approximate optimization
Shaydulin, R., Safro, I., & Larson, J. (2019) · 2019 IEEE High Performance Extreme Computing Conference (HPEC) · doi:10.1109/hpec.2019.8916288 · Cited by 110
Benchmarking the quantum approximate optimization algorithm
Willsch, M., Willsch, D., Jin, F., Raedt, H. A. D., & Michielsen, K. F. L. (2020) · RWTH Publications (RWTH Aachen) · Cited by 109
Gate-Efficient Simulation of Molecular Eigenstates on a Quantum Computer
Ganzhorn, M., Egger, D. J., Tavernelli, I., Filipp, S., Barkoutsos, P. K., Ollitrault, P. J., Salis, G., Moll, N., Roth, M., Fuhrer, A., et al. (2019) · RWTH Publications (RWTH Aachen) · Cited by 109
Self-citationQiskit Backend Specifications for OpenQASM and OpenPulse ExperimentsPreprint
McKay, D. C., Alexander, T., Bello, L., Biercuk, M. J., Bishop, L. S., Chen, J., Chow, J. M., Corcoles, A. D., Egger, D. J., Filipp, S., et al. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1809.03452 · Cited by 101
Self-citationOptimized Quantum Compilation for Near-Term Algorithms with OpenPulse
Gokhale, P., Javadi-Abhari, A., Earnest, N., Shi, Y., & Chong, F. T. (2020) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1109/micro50266.2020.00027 · Cited by 101
Quantum SDP-Solvers: Better upper and lower bounds
van Apeldoorn, J., Gilyén, A., Gribling, S., & de Wolf, R. (2020) · Quantum · doi:10.22331/q-2020-02-14-230 · Cited by 100
Majumdar, A., Hall, G., & Ahmadi, A. A. (2019) · Annual Review of Control Robotics and Autonomous Systems · doi:10.1146/annurev-control-091819-074326 · Cited by 97
Classical and Quantum Bounded Depth Approximation Algorithms
Hastings, M. B. (2019) · arXiv · doi:10.48550/arxiv.1905.07047 · Cited by 96
Pulse-efficient circuit transpilation for quantum applications on cross-resonance-based hardware
Earnest, N., Tornow, C., & Egger, D. J. (2021) · Physical Review Research · doi:10.1103/physrevresearch.3.043088 · Cited by 94
Self-citationQuantum Algorithms for Fixed Qubit Architectures
Farhi, E., Goldstone, J., Gutmann, S., & Neven, H. (2017) · arXiv · doi:10.48550/arxiv.1703.06199 · Cited by 93
Warm start of the primal-dual method applied in the cutting-plane scheme
Gondzio, J. (1998) · Mathematical Programming · doi:10.1007/bf02680554 · Cited by 91
Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets
Lacroix, N., Hellings, C., Andersen, C. K., Paolo, A. D., Remm, A., Lazar, S., Krinner, S., Norris, G. J., Gabureac, M. S., Heinsoo, J., et al. (2020) · PRX Quantum · doi:10.1103/prxquantum.1.020304 · Cited by 89
Scalable Semidefinite Programming
Yurtsever, A., Tropp, J. A., Fercoq, O., Udell, M. R., & Cevher, V. (2019) · CaltechAUTHORS (California Institute of Technology) · Cited by 89
Brandao, F. G. S. L., Broughton, M., Farhi, E., Gutmann, S., & Neven, H. (2018) · arXiv · doi:10.48550/arxiv.1812.04170 · Cited by 88
On the Complexity of Semidefinite Programs
Porkolab, L., & Khachiyan, L. (1997) · Journal of Global Optimization · doi:10.1023/a:1008203903341 · Cited by 85
Unique Games with Entangled Provers Are Easy
Kempe, J., Regev, O., & Toner, B. (2010) · SIAM Journal on Computing · doi:10.1137/090772885 · Cited by 85
Khot, S., & Vishnoi, N. K. (2015) · Journal of the ACM · doi:10.1145/2629614 · Cited by 83
Bridging Classical and Quantum with SDP initialized warm-starts for QAOA
Tate, R., Farhadi, M., Herold, C. D., Mohler, G., & Gupta, S. (2022) · ACM Transactions on Quantum Computing · doi:10.1145/3549554 · Cited by 81
Reinforcement-learning-assisted quantum optimization
Wauters, M. M., Panizon, E., Mbeng, G. B., & Santoro, G. E. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.033446 · Cited by 80
Random MAX SAT, random MAX CUT, and their phase transitions
Coppersmith, D., Gamarnik, D., Hajiaghayi, M., & Sorkin, G. B. (2004) · Random Structures and Algorithms · doi:10.1002/rsa.20015 · Cited by 79
The detectability lemma and quantum gap amplification
Aharonov, D., Arad, I., Landau, Z. A., & Vazirani, U. V. (2009) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1536414.1536472 · Cited by 77
A polynomial case of unconstrained zero-one quadratic optimization
Allemand, K., Fukuda, K., Liebling, T. M., & Steiner, E. (2001) · Mathematical Programming · doi:10.1007/s101070100233 · Cited by 76
On the Unique Games Conjecture (Invited Survey)
Khot, S. (2010) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2010.19 · Cited by 76
Toward pricing financial derivatives with an IBM quantum computer
Martin, A., Candelas, B., Rodríguez-Rozas, Á., Martín-Guerrero, J. D., Chen, X., Lamata, L., Orús, R., Solano, E., & Sanz, M. (2021) · Physical Review Research · doi:10.1103/physrevresearch.3.013167 · Cited by 74
How Good is the Goemans--Williamson MAX CUT Algorithm?
Karloff, H. J. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539797321481 · Cited by 71
Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion
Subhash, K., Minzer, D., & Safra, M. (2018) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2018.00062 · Cited by 70
Efficient State Preparation for Quantum Amplitude Estimation
Vazquez, A. C., & Woerner, S. (2021) · Physical Review Applied · doi:10.1103/physrevapplied.15.034027 · Cited by 63
Self-citationQuantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning
Brandão, F. G. S. L., Kalev, A., Li, T., Lin, C. Y.-Y., Svore, K. M., & Wu, X. (2019) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.icalp.2019.27 · Cited by 60
Raghavendra, P., & Steurer, D. (2009) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2009.74 · Cited by 59
Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets
Lacroix, N., Hellings, C., Andersen, C. K., Paolo, A. D., Remm, A., Lazar, S., Krinner, S., Norris, G. J., Gabureac, M. S., Heinsoo, J., et al. (2020) · Repository for Publications and Research Data (ETH Zurich) · doi:10.3929/ethz-b-000464528 · Cited by 59
Evaluating Quantum Approximate Optimization Algorithm: A Case Study
Shaydulin, R., & Alexeev, Y. (2019) · 2019 Tenth International Green and Sustainable Computing Conference (IGSC) · doi:10.1109/igsc48788.2019.8957201 · Cited by 55
Quantum Algorithms for Mixed Binary Optimization Applied to Transaction Settlement
Braine, L., Egger, D. J., Glick, J., & Woerner, S. (2021) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3063635 · Cited by 51
Self-citationQuantum Annealing versus Digital Computing
Jünger, M., Lobe, E., Mutzel, P., Reinelt, G., Rendl, F., Rinaldi, G., & Stollenwerk, T. (2021) · ACM Journal of Experimental Algorithmics · doi:10.1145/3459606 · Cited by 51
Local classical MAX-CUT algorithm outperforms p=2 QAOA on high-girth regular graphs
Marwaha, K. (2021) · Quantum · doi:10.22331/q-2021-04-20-437 · Cited by 49
Random MAX SAT, Random MAX CUT, and Their Phase TransitionsPreprint
Coppersmith, D., Gamarnik, D., Hajiaghayi, M., & Sorkin, G. B. (2003) · arXiv (Cornell University) · doi:10.48550/arxiv.math/0306047 · Cited by 47
Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA
Natarajan, A., & Vidick, T. (2018) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2018.00075 · Cited by 39
Unique Games with Entangled Provers are Easy
Kempe, J., Regev, O., & Toner, B. (2008) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.9 · Cited by 38
Quantum Annealing: a journey through Digitalization, Control, and hybrid Quantum Variational schemesPreprint
Mbeng, G. B., Fazio, R., & Santoro, G. E. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.08948 · Cited by 35
Lower bounds on circuit depth of the quantum approximate optimization algorithm
Herrman, R., Ostrowski, J., Humble, T. S., & Siopsis, G. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03001-7 · Cited by 35
Alam, M., Ash-Saki, A., & Ghosh, S. (2019) · arXiv · doi:10.48550/arxiv.1907.09631 · Cited by 33
A MAX-CUT formulation of 0/1 programs
Lasserre, J. B. (2015) · Operations Research Letters · doi:10.1016/j.orl.2015.12.014 · Cited by 32
Second-Order Cone Relaxations for Binary Quadratic Polynomial Programs
Ghaddar, B., Vera, J. C., & Anjos, M. F. (2011) · SIAM Journal on Optimization · doi:10.1137/100802190 · Cited by 21
Robust Control Optimization for Quantum Approximate Optimization Algorithms
Dong, Y., Meng, X., Lin, L., Kosut, R. L., & Whaley, K. B. (2020) · IFAC-PapersOnLine · doi:10.1016/j.ifacol.2020.12.130 · Cited by 19
Gondzio, J., & Grothey, A. (2006) · WIT transactions on modelling and simulation · doi:10.2495/cf060101 · Cited by 15
Lodewijks, B. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1911.08043 · Cited by 15
Quantum-Inspired Sublinear Algorithm for Solving Low-Rank Semidefinite Programming.
Chia, N.-H., Li, T., Lin, H. H., & Wang, C. (2020) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.mfcs.2020.23 · Cited by 10
Subexponential LPs Approximate Max-Cut
Hopkins, S. B., Schramm, T., & Trevisan, L. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00092 · Cited by 9
Fair Dimensionality Reduction and Iterative Rounding for SDPsPreprint
Morgenstern, J., Samadi, S., Singh, M., Tantipongpipat, U. T., & Vempala, S. (2019) · arXiv (Cornell University) · Cited by 8
Krivine diffusions attain the Goemans--Williamson approximation ratioPreprint
Eldan, R., & Naor, A. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1906.10615 · Cited by 7
Entropy-Penalized Semidefinite Programming
Krechetov, M., Mareček, J., Maximov, Y., & Takáč, M. (2019) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2019/157 · Cited by 6
Self-citationLarkin, J. M., Jonsson, M., Justice, D., & Guerreschi, G. G. (2020) · arXiv (Cornell University) · Cited by 6
The Unique Games Conjecture with Entangled Provers is False
Kempe, J., Regev, O., & Toner, B. (2008) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · doi:10.4230/dagsemproc.07411.6 · Cited by 5
Reachability Deficits Implicit in Google's Quantum Approximate Optimization of Graph ProblemsPreprint
Akshay, V., Philathong, H., Zacharov, I., & Biamonte, J. (2020) · arXiv (Cornell University) · Cited by 5
Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
Zadeh, S. A., Bansal, N., Guruganesh, G., Nikolov, A., Schwartz, R., & Singh, M. (2019) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611975994.52 · Cited by 4
A new polynomially solvable class of quadratic optimization problems with box constraints
Hladík, M., Černý, M., & Rada, M. (2021) · Optimization Letters · doi:10.1007/s11590-021-01711-6 · Cited by 1
Research works printed but not linked: 4
- Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm, 2014a. URL https://arxiv.org/abs/1411.4028. · arXiv
- Michael Juenger, Elisabeth Lobe, Petra Mutzel, Gerhard Reinelt, Franz Rendl, Giovanni Rinaldi, and Tobias Stollenwerk. Performance of a quantum annealer for Ising ground state computations on chimera graphs, 2019. URL https://arxiv.org/abs/1904.11965. · arXiv
- Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Hybrid quantum-classical algorithms for approximate graph coloring, 2020b. URL https://arxiv.org/abs/2011.13420. · arXiv
- Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge university press, 2017.
Cited by
Sorted by citations
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 2,231
A review on Quantum Approximate Optimization Algorithm and its variants
Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.-H., Pandya, K., & Summer, A. (2024) · Physics Reports · doi:10.1016/j.physrep.2024.03.002 · Cited by 563
Quantum Computing for High-Energy Physics: State of the Art and Challenges
Meglio, A. D., Jansen, K., Tavernelli, I., Alexandrou, C., Arunachalam, S., Bauer, C., Borras, K., Carrazza, S., Crippa, A., Croft, V. A., et al. (2024) · PRX Quantum · doi:10.1103/prxquantum.5.037001 · Cited by 359
Self-citationChallenges and opportunities in quantum optimization
Abbas, A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D. J., Elmegreen, B. G., et al. (2024) · Nature Reviews Physics · doi:10.1038/s42254-024-00770-9 · Cited by 201
Self-citationNoisy intermediate-scale quantum (NISQ) algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2021) · arXiv · doi:10.48550/arxiv.2101.08448 · Cited by 166
Metadata
- Authors
- Egger, D. J., Mareček, J., & Woerner, S.
- Affiliations
- IBM Research - Zurich (CH)
- Czech Technical University in Prague (CZ)
- Venue
- Quantum
- Published
- 2021-06-17
- Volume
- 5
- Pages
- 479
- ISSN
- 2521-327X (ISSN-L)
- OpenAlex
- W3088409280
- Cited by
- 269
- References
- 122
- Citations by year
- 2026: 44 · 2025: 61 · 2024: 57 · 2023: 56 · 2022: 34 · 2021: 16
- FWCI
- 14.35
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Locations
- Quantum (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- arXiv (Cornell University) (cc-by)
- Bulletin of the American Physical Society
- Funders
- OP RDE project Research Center for Informatic (CZ.02.1.01/0.0/0.0/16_019/0000765)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Keywords
- warm start, quantum optimization, quantum approximate optimization algorithm, MaxCut, portfolio optimization, semidefinite relaxation, Unique Games Conjecture, randomized rounding, integer programming, combinatorial optimization, performance guarantees
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
