From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz

L. Lovász, “Coverings and colorings of hypergraphs,” in Proc. 4th Southeastern Conference on Combinatorics, Graph Theory, and Computing . Utilitas Mathematica Publishing, Winnipeg, 1973, pp. 3–12

1973

Earlier work this paper cites.

D. S. Johnson, “Approximation algorithms for combinatorial problems,” in Proceedings of the fifth annual ACM symposium on Theory of computing . ACM, 1973, pp. 38–49

1973

Earlier work this paper cites.

N. Christofides, “Worst-case analysis of a new heuristic for the travelling salesman problem,” Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group, Tech. Rep., 1976

1976

Earlier work this paper cites.

J. K. Lenstra, A. R. Kan, and P. Brucker, “Complexity of machine scheduling problems,” Annals of discrete mathematics , vol. 1, pp. 343–362, 1977

1977

Earlier work this paper cites.

A. Panconesi and D. Ranjan, “Quantifiers and approximation,” in Proceedings of the twenty-second annual ACM symposium on Theory of computing . ACM, 1990, pp. 446–456

1990

Earlier work this paper cites.

T. Nishizeki and K. Kashiwagi, “On the 1.1 edge-coloring of multigraphs,” SIAM Journal on Discrete Mathematics , vol. 3, no. 3, pp. 391–410, 1990

1990

Earlier work this paper cites.

P. Orponen and H. Mannila, “On approximation preserving reductions: Complete problems and robust measures (revised version),” Department of Computer Science, University of Helsinki , 1990

1990

Earlier work this paper cites.

C. Papadimitriou and M. Yannakakis, “Optimization, approximation, and complexity classes,” Journal of Computer and System Sciences , vol. 43, pp. 425–440, 1991

1991

Earlier work this paper cites.

R. Boppana and M. M. Halldórsson, “Approximating maximum independent sets by excluding subgraphs,” BIT Numerical Mathematics , vol. 32, no. 2, pp. 180–196, 1992

1992

Earlier work this paper cites.

——, “A still better performance guarantee for approximate graph coloring,” Information Processing Letters , vol. 45, no. 1, pp. 19–23, 1993

1993

Earlier work this paper cites.

C. H. Papadimitriou and M. Yannakakis, “The traveling salesman problem with distances one and two,” Mathematics of Operations Research , vol. 18, no. 1, pp. 1–11, 1993

1993

Earlier work this paper cites.

C. H. Papadimitriou, “Computational Complexity,” 1994

1994

Earlier work this paper cites.

R. Kohli, R. Krishnamurti, and P. Mirchandani, “The minimum satisfiability problem,” SIAM Journal on Discrete Mathematics , vol. 7, no. 2, pp. 275–283, 1994

1994

Earlier work this paper cites.

E. Petrank, “The hardness of approximation: Gap location,” Computational Complexity , vol. 4, no. 2, pp. 133–157, 1994

1994

Earlier work this paper cites.

C. Lund and M. Yannakakis, “On the hardness of approximating minimization problems,” Journal of the ACM (JACM) , vol. 41, no. 5, pp. 960–981, 1994

1994

Earlier work this paper cites.

M. X. Goemans and D. P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” Journal of the ACM (JACM) , vol. 42, no. 6, pp. 1115–1145, 1995

1995

Earlier work this paper cites.

M. M. Halldórsson, “Approximating discrete collections via local improvements.” in SODA , vol. 95, 1995, pp. 160–169

1995

Earlier work this paper cites.

D. Zuckerman, “On unapproximable versions of NP-complete problems,” SIAM Journal on Computing , vol. 25, no. 6, pp. 1293–1304, 1996

1996

Earlier work this paper cites.

N. Ueda and T. Nagao, “NP-completeness Results for NONOGRAM via Parsimonious Reductions,” Tokyo Institute of Technology, Tech. Rep., 1996

1996

Earlier work this paper cites.

M. V. Marathe and S. Ravi, “On approximation algorithms for the minimum satisfiability problem,” Information Processing Letters , vol. 58, no. 1, pp. 23–29, 1996

1996

Earlier work this paper cites.

H. Karloff and U. Zwick, “A 7/8-approximation algorithm for MAX 3SAT?” in Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on . IEEE, 1997, pp. 406–415

1997

Earlier work this paper cites.

A. Frieze and M. Jerrum, “Improved approximation algorithms for MAXk-CUT and MAX BISECTION,” Algorithmica , vol. 18, no. 1, pp. 67–81, 1997

1997

Earlier work this paper cites.

S. Khanna, R. Motwani, M. Sudan, and U. Vazirani, “On syntactic versus computational views of approximability,” SIAM Journal on Computing , vol. 28, no. 1, pp. 164–191, 1998

1998

Earlier work this paper cites.

G. Andersson and L. Engebretsen, “Better approximation algorithms for Set splitting and Not-All-Equal SAT,” Information Processing Letters , vol. 65, no. 6, pp. 305–311, 1998

1998

Earlier work this paper cites.

U. Zwick, “Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint.” in SODA , vol. 98, 1998, pp. 201–210

1998

Earlier work this paper cites.

D. Bertsimas, C. Teo, and R. Vohra, “On dependent randomized rounding algorithms,” Operations Research Letters , vol. 24, no. 3, pp. 105–114, 1999

1999

Earlier work this paper cites.

M. M. Halldórsson, J. Kratochvıl, and J. A. Telle, “Independent sets with domination constraints,” Discrete Applied Mathematics , vol. 99, no. 1, pp. 39–54, 2000

2000

Earlier work this paper cites.

D. Gottesman, A. Kitaev, and J. Preskill, “Encoding a qubit in an oscillator,” Physical Review A , vol. 64, no. 1, p. 012310, 2001

2001

Earlier work this paper cites.

J. Håstad, “Some optimal inapproximability results,” J. ACM , vol. 48, no. 4, pp. 798–859, Jul. 2001

2001

Earlier work this paper cites.

S. D. Bartlett, H. de Guise, and B. C. Sanders, “Quantum encodings in spin systems and harmonic oscillators,” Physical Review A , vol. 65, no. 5, p. 052316, 2002

2002

Earlier work this paper cites.

U. Feige, M. Karpinski, and M. Langberg, “Improved approximation of max-cut on graphs of bounded degree,” Journal of Algorithms , vol. 43, no. 2, pp. 201–219, 2002

2002

Earlier work this paper cites.

M. Lewin, D. Livnat, and U. Zwick, “Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems,” in International Conference on Integer Programming and Combinatorial Optimization . Springer, 2002, pp. 67–82

2002

Cited alongside, same era.

I. Dinur and S. Safra, “The importance of being biased,” in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing . ACM, 2002, pp. 33–42

2002

Cited alongside, same era.

M. X. Goemans, M. Queyranne, A. S. Schulz, M. Skutella, and Y. Wang, “Single machine scheduling with release dates,” SIAM Journal on Discrete Mathematics , vol. 15, no. 2, pp. 165–192, 2002

2002

Cited alongside, same era.

T. Yato and T. Seta, “Complexity and completeness of finding another solution and its application to puzzles,” IEICE transactions on fundamentals of electronics, communications and computer sciences , vol. 86, no. 5, pp. 1052–1060, 2003

2003

Cited alongside, same era.

S. Boixo, V. N. Smelyanskiy, A. Shabani, S. V. Isakov, M. Dykman, V. S. Denchev, M. H. Amin, A. Y. Smirnov, M. Mohseni, and H. Neven, “Computational multiqubit tunnelling in programmable quantum annealers,” Nature Communications , vol. 7, 01 2016

2016

Later among the works it cites.

E. A. Sete, W. J. Zeng, and C. T. Rigetti, “A functional architecture for scalable quantum computing,” in 2016 IEEE International Conference on Rebooting Computing (ICRC) , Oct 2016, pp. 1–6

2016

Later among the works it cites.

S. Debnath, N. Linke, C. Figgatt, K. Landsman, K. Wright, and C. Monroe, “Demonstration of a small programmable quantum computer with atomic qubits,” Nature , vol. 536, no. 7614, pp. 63–66, 2016

2016

Later among the works it cites.

M. Saffman, “Quantum computing with atomic qubits and rydberg interactions: progress and challenges,” Journal of Physics B: Atomic, Molecular and Optical Physics , vol. 49, no. 20, p. 202001, 2016

2016

Later among the works it cites.