Synergies Between Operations Research and Quantum Information Science

References

• Aaronson S (2015) Read the fine print. Nature Phys. 11(4):291–293.Crossref, Google Scholar
• Aaronson S (2021) Open problems related to quantum query complexity. ACM Trans. Quantum Comput. 2(4):1–9.Crossref, Google Scholar
• Aaronson S (2022) How much structure is needed for huge quantum speedups? Preprint, submitted September 14, https://arxiv.org/abs/2209.06930.Google Scholar
• Aaronson S, Chen L (2016) Complexity-theoretic foundations of quantum supremacy experiments. Preprint, submitted December 18, https://arxiv.org/abs/1612.05903.Google Scholar
• Aharonov D, Gao X, Landau Z, Liu Y, Vazirani U (2022) A polynomial-time classical algorithm for noisy random circuit sampling. Preprint, submitted November 8, https://arxiv.org/abs/2211.03999.Google Scholar
• Anshu A, Metger T (2022) Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations. Preprint, submitted December 20, https://arxiv.org/abs/2209.02715.Google Scholar
• Anshu A, Gosset D, Morenz K (2020) Beyond product state approximations for a quantum analogue of Max Cut. Proc. 15th Conf. on the Theory of Quantum Comput., Comm., and Cryptography (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, Germany).Google Scholar
• Anshu A, Gosset D, Korol KJM, Soleimanifar M (2021) Improved approximation algorithms for bounded-degree local Hamiltonians. Phys. Rev. Lett. 127(25):250502.Crossref, Google Scholar
• Arunachalam S, Briët J, Palazuelos C (2019) Quantum query algorithms are completely bounded forms. SIAM J. Comput. 48(3):903–925.Crossref, Google Scholar
• Arute F, Arya K, Babbush R, Bacon D, Bardin JC, Barends R, Biswas R, et al. (2019) Quantum supremacy using a programmable superconducting processor. Nature 574(7779):505–510.Crossref, Google Scholar
• Augustino B, Nannicini G, Terlaky T, Zuluaga LF (2021) Quantum interior point methods for semidefinite optimization. Preprint, submitted December 11, https://arxiv.org/abs/2112.06025.Google Scholar
• Banchi L, Pereira J, Lloyd S, Pirandola S (2020) Convex optimization of programmable quantum computers. NPJ Quantum Inform. 6(1):1–10.Google Scholar
• Barnum H, Saks M, Szegedy M (2003) Quantum query complexity and semi-definite programming. Proc. 18th IEEE Annual Conf. on Comput. Complexity (IEEE, Piscataway, NJ), 179–193.Google Scholar
• Ben-David S, Childs AM, Gilyén A, Kretschmer W, Podder S, Wang D (2020) Symmetries, graph properties, and quantum speedups. Proc. IEEE 61st Annual Sympos. on Foundations of Comput. Sci. (IEEE, Piscataway, NJ), 649–660.Google Scholar
• Berta M, Borderi F, Fawzi O, Scholz VB (2022) Semidefinite programming hierarchies for constrained bilinear optimization. Math. Programming 194:781–829.Crossref, Google Scholar
• Biamonte J, Wittek P, Pancotti N, Rebentrost P, Wiebe N, Lloyd S (2017) Quantum machine learning. Nature 549(7671):195–202.Crossref, Google Scholar
• Bravyi S, Kliesch A, Koenig R, Tang E (2020) Obstacles to variational quantum optimization from symmetry protection. Phys. Rev. Lett. 125(26):260505.Crossref, Google Scholar
• Brunner N, Cavalcanti D, Pironio S, Scarani V, Wehner S (2014) Bell nonlocality. Rev. Modern Phys. 86(2):419.Crossref, Google Scholar
• Chakrabarti S, Childs AM, Li T, Wu X (2020) Quantum algorithms and lower bounds for convex optimization. Quantum 4:221.Crossref, Google Scholar
• Chen S, Cotler J, Huang HY, Li J (2022) The complexity of NISQ. Preprint, submitted October 13, https://arxiv.org/abs/2210.07234.Google Scholar
• Chia NH, Gilyén A, Li T, Lin HH, Tang E, Wang C (2020) Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. Proc. 52nd Annual ACM SIGACT Sympos. on Theory of Comput. (ACM, New York), 387–400.Google Scholar
• Chou CN, Love PJ, Sandhu JS, Shi J (2022) Limitations of local quantum algorithms on random Max-k-XOR and beyond. Proc. 49th Internat. Colloquium on Automata, Languages, and Programming (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, Germany).Google Scholar
• Cotler J, Huang HY, McClean JR (2021) Revisiting dequantization and quantum advantage in learning tasks. Preprint, submitted December 6, https://arxiv.org/abs/2112.00811.Google Scholar
• DeLorenzo K, Kimmel S, Witter RT (2019) Applications of the quantum algorithm for st-connectivity. Proc. 14th Conf. on the Theory of Quantum Comput., Comm., and Cryptography (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany).Google Scholar
• Dervovic D, Herbster M, Mountney P, Severini S, Usher N, Wossnig L (2018) Quantum linear systems algorithms: A primer. Preprint, submitted February 22, https://arxiv.org/abs/1802.08227.Google Scholar
• Deza MM, Laurent M (1997) Geometry of Cuts and Metrics (Springer, Berlin).Crossref, Google Scholar
• DIMACS (2022) DIMACS implementation challenges. Accessed December 6, 2022, http://dimacs.rutgers.edu/programs/challenge/.Google Scholar
• Eisert J, Hangleiter D, Walk N, Roth I, Markham D, Parekh R, Chabaud U, et al. (2020) Quantum certification and benchmarking. Nature Rev. Phys. 2(7):382–390.Crossref, Google Scholar
• Farhi E, Goldstone J, Gutmann S (2014) A quantum approximate optimization algorithm. Preprint, submitted November 14, https://arxiv.org/abs/1411.4028.Google Scholar
• Fawzi H, Saunderson J (2022) Optimal self-concordant barriers for quantum relative entropies. Preprint, submitted June 28, https://arxiv.org/abs/2205.04581.Google Scholar
• Fei X, Brady LT, Larson J, Leyffer S, Shen S (2022) Binary control pulse optimization for quantum systems. Preprint, submitted December 8, https://arxiv.org/abs/2204.05773.Google Scholar
• Fiorini S, Massar S, Pokutta S, Tiwary HR, De Wolf R (2015) Exponential lower bounds for polytopes in combinatorial optimization. J. ACM 62(2):1–23.Crossref, Google Scholar
• Fletcher AS, Shor PW, Win MZ (2007) Optimum quantum error recovery using semidefinite programming. Phys. Rev. A 75(1):012338.Crossref, Google Scholar
• Garg A, Kothari R, Netrapalli P, Sherif S (2021) Near-optimal lower bounds for convex optimization for all orders of smoothness. Adv. Neural Inform. Processing Systems 34:29874–29884.Google Scholar
• Gharibian S, Parekh O (2019) Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany).Google Scholar
• Gilyén A, Arunachalam S, Wiebe N (2019) Optimizing quantum optimization algorithms via faster quantum gradient computation. Proc. 30th Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 1425–1444.Google Scholar
• Goemans MX, Williamson DP (1995) Improved approximation algorithms for Maximum Cut and satisfiability problems using semidefinite programming. J. ACM 42(6):1115–1145.Crossref, Google Scholar
• Gribling S, Laurent M (2019) Semidefinite programming formulations for the completely bounded norm of a tensor. Preprint, submitted January 15, https://arxiv.org/abs/1901.04921.Google Scholar
• Gribling S, Polak S (2021) Mutually unbiased bases: Polynomial optimization and symmetry. Preprint, submitted November 10, https://arxiv.org/abs/2111.05698.Google Scholar
• Hadfield SA (2018) Quantum Algorithms for Scientific Computing and Approximate Optimization (Columbia University, New York).Google Scholar
• Harrow A (2022) Where can I learn about quantum information? Accessed December 6, 2022, https://web.mit.edu/aram/www/advice/quantum.html.Google Scholar
• Huang B, Jiang S, Song Z, Tao R, Zhang R (2022) A faster quantum algorithm for semidefinite programming via robust IPM framework. Preprint, submitted July 22, https://arxiv.org/abs/2207.11154.Google Scholar
• Hwang Y, Neeman J, Parekh O, Thompson K, Wright J (2021) Unique games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell’s inequality. Proc. 2023 Annual ACM-SIAM Symp. Discrete Algorithms (ACM-SIAM), 1319–1384.Google Scholar
• Jain R, Ji Z, Upadhyay S, Watrous J (2010) QIP=PSPACE. Comm. ACM 53(12):102–109.Crossref, Google Scholar
• Ji Z, Natarajan A, Vidick T, Wright J, Yuen H (2021) MIP*= RE. Comm. ACM 64(11):131–138.Crossref, Google Scholar
• Kalai G (2020) The argument against quantum computers. Quantum, Probability, Logic (Springer, Berlin), 399–422.Crossref, Google Scholar
• Kaniewski J, Lee T, Wolf RD (2015) Query complexity in expectation. International Colloquium on Automata, Languages, and Programming (Springer, Berlin), 761–772.Crossref, Google Scholar
• Kerenidis I, Prakash A (2020) Quantum gradient descent for linear systems and least squares. Phys. Rev. A 101(2):022316.Crossref, Google Scholar
• Kerenidis I, Prakash A, Szilágyi D (2021) Quantum algorithms for second-order cone programming and support vector machines. Quantum 5:427.Crossref, Google Scholar
• Khot S, Kindler G, Mossel E, O’Donnell R (2007) Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput. 37(1):319–357.Crossref, Google Scholar
• Kliesch M, Roth I (2021) Theory of quantum system certification. PRX Quantum 2(1):010201.Crossref, Google Scholar
• Kosut RL, Lidar DA (2009) Quantum error correction via convex optimization. Quantum Inform. Processing 8(5):443–459.Crossref, Google Scholar
• Madsen LS, Laudenbach F, Askarani MF, Rortais F, Vincent T, Bulmer JF, Miatto FM, et al. (2022) Quantum computational advantage with a programmable photonic processor. Nature 606(7912):75–81.Crossref, Google Scholar
• Marwaha K, Hadfield S (2022) Bounds on approximating Max kXOR with quantum and classical local algorithms. Quantum 6:757.Crossref, Google Scholar
• Matthews D (2021) How to get started in quantum computing. Nature 591(7848):166–167.Crossref, Google Scholar
• Minkel J (2009) Strange but true: Superfluid helium can climb walls. Sci. Amer. 300:2.Google Scholar
• Mittelmann HD, Spellucci P (2021) Decision tree for optimization software. http://plato.asu.edu/guide.html.Google Scholar
• Montanaro A, de Wolf R (2016) A survey of quantum property testing. Theory Comput. 1–81.Crossref, Google Scholar
• Morvan A, Chen L, Larson JM, Santiago DI, Siddiqi I (2022) Optimizing frequency allocation for fixed-frequency superconducting quantum processors. Phys. Rev. Res. 4(2):023079.Crossref, Google Scholar
• Mousavi H, Nezhadi SS, Yuen H (2021) Nonlocal games, compression theorems, and the arithmetical hierarchy. Preprint, submitted October 12, https://arxiv.org/abs/2110.04651.Google Scholar
• Nagarajan H, Lockwood O, Coffrin C (2021) QuantumCircuitOpt: An open-source framework for provably optimal quantum circuit design. Proc. IEEE/ACM 2nd Internat. Workshop on Quantum Comput. Software (IEEE, Piscataway, NJ), 55–63.Google Scholar
• Nannicini G (2022) Fast quantum subroutines for the simplex method. Oper. Res. Accessed December 6, 2022, https://pubsonline.informs.org/doi/abs/10.1287/opre.2022.2341?journalCode=opre.Link, Google Scholar
• Nannicini G, Bishop LS, Günlük O, Jurcevic P (2022) Optimal qubit assignment and routing via integer programming. ACM Trans. Quantum Comput. 4(1):1–31.Crossref, Google Scholar
• Nielsen MA, Chuang IL (2010) Quantum Computation and Quantum Information (Cambridge University Press, Cambridge, UK).Google Scholar
• Palazuelos C, Vidick T (2016) Survey on nonlocal games and operator space theory. J. Math. Phys. 57(1):015220.Crossref, Google Scholar
• Parekh O, Thompson K (2021a) Application of the level-2 quantum Lasserre hierarchy in quantum approximation algorithms. Proc. 48th Internat. Colloquium on Automata, Languages, and Programming (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, Germany).Google Scholar
• Parekh O, Thompson K (2021b) Beating random assignment for approximating quantum 2-local Hamiltonian problems. Proc. 29th Annual Eur. Sympos. on Algorithms (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, Germany).Google Scholar
• Parekh O, Thompson K (2022) An optimal product-state approximation for 2-local quantum Hamiltonians with positive terms. Preprint, submitted June 16, https://arxiv.org/abs/2206.08342.Google Scholar
• Pironio S, Navascués M, Acin A (2010) Convergent relaxations of polynomial optimization problems with noncommuting variables. SIAM J. Optim. 20(5):2157–2180.Crossref, Google Scholar
• Preskill J (2018) Quantum computing in the NISQ era and beyond. Quantum 2:79.Crossref, Google Scholar
• Reichardt BW (2011) Reflections for quantum query algorithms. Proc. 22nd Annual ACM-SIAM Sympos. on Discrete Algorithms (SIAM, Philadelphia), 560–569.Crossref, Google Scholar
• Siddhu V, Tayur S (2021) Five starter pieces: Quantum information science via semi-definite programs. Preprint, submitted December 15, https://arxiv.org/abs/2112.08276.Google Scholar
• Tang E (2019) A quantum-inspired classical algorithm for recommendation systems. Proc. 51st Annual ACM SIGACT Sympos. on Theory of Comput., 217–228.Crossref, Google Scholar
• Tang W, Tomesh T, Suchara M, Larson J, Martonosi M (2021) CutQC: Using small quantum computers for large quantum circuit evaluations. Proc. 26th ACM Internat. Conf. on Architectural Support for Programming Languages and Operating Systems (ACM, New York), 473–486.Google Scholar
• van Apeldoorn J, Gilyén A, Gribling S, de Wolf R (2020) Convex optimization using quantum oracles. Quantum 4:220.Crossref, Google Scholar
• Wilczek F (2016) Entanglement made simple. Quanta Magazine. Accessed December 6, 2022, https://www.quantamagazine.org/entanglement-made-simple-20160428/.Google Scholar