Quantum Speed-ups for Semidefinite Programming

E.T. Jaynes. Information Theory and Statistical Mechanics II. Phys. Rev. 108, 171 (1957)

1957

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 42, 1115 (1995)

1995

Earlier work this paper cites.

L. Vandenberghe and S. Boyd. Semidefinite programming. SIAM Review 38, 49 (1996)

1996

Earlier work this paper cites.

L.K. Grover. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 79, 325 (1997)

1997

Earlier work this paper cites.

M.X. Goemans. Semidefinite programming in combinatorial optimization. Mathematical Programming 79, 143 (1997)

1997

Earlier work this paper cites.

P.W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review 41.2, 303 (1999)

1999

Earlier work this paper cites.

H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Phys. Rev. Lett. 87(16):167902, 2001. quant-ph/0102001

2001

Earlier work this paper cites.

G. Brassard et al. Quantum amplitude amplification and estimation. Contemporary Mathematics 305, 53 (2002)

2002

Earlier work this paper cites.

R. Ahlswede, A. Winter. Strong Converse for Identification via Quantum Channels". IEEE Trans. Information Theory 48, 569 (2003)

2003

Earlier work this paper cites.

S. Boyd and L. Vandenberghe. Convex optimization. Cambridge University Press, 2004

2004

Cited alongside, same era.

S. Arora, E. Hazan and S. Kale. Fast algorithms for approximate semidefinite programming using the multiplicative weights update method. 46th Annual IEEE Symposium on Foundations of Computer Science, 2005. FOCS 2005

2005

Cited alongside, same era.

W.R. Gilks. Markov chain monte carlo. John Wiley and Sons, Ltd. Chicago (2005)

2005

Cited alongside, same era.

S. Arora and S. Kale. A combinatorial, primal-dual approach to semidefinite programs. Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. ACM, 2007

2007

Cited alongside, same era.

D. Poulin and P. Wocjan. Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer. Phys. Rev. Lett. 103, 220502 (2009)

2009

M.H. Yung and A. Aspuru-Guzik. A quantum–quantum Metropolis algorithm. Proceedings of the National Academy of Sciences 109, 754 (2012)

2012

Later among the works it cites.

S. Lloyd, M. Mohseni, P. Rebentrost. Quantum Principal Component Analysis. Nature Physics 10, 631 (2014)

2014

Later among the works it cites.

Y.T. Lee, A. Sidford, and S.C. Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. IEEE 56th Annual Symposium on the Foundations of Computer Science (FOCS), 2015

2015

Later among the works it cites.

J.R. Lee, P. Raghavendra, and D. Steurer. Lower bounds on the size of semidefinite programming relaxations. Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing. ACM, 2015

2015

Later among the works it cites.