About

Giacomo Nannicini is an Associate Professor in the Daniel J. Epstein Department of Industrial & Systems Engineering at USC Viterbi School of Engineering. His main research and teaching interests are in optimization, broadly defined, and its applications. He is particularly interested in algorithms, software, and models of computation, including quantum computing. Nannicini obtained a PhD from Ecole Polytechnique in Paris, located in Palaiseau, and has worked as a postdoctoral fellow at Carnegie Mellon University Tepper School of Business and MIT Sloan School of Management. He has also served as an Assistant Professor at the Singapore University of Technology and Design within the Engineering Systems & Design pillar and worked at the IBM T.J. Watson Research Center in the quantum algorithms group before joining USC. Throughout his career, he has received several awards, including the 2021 Beale–Orchard-Hays prize, the best paper award at IEEE QCE 2021, the 2016 COIN-OR Cup, the 2015 Robert Faure prize, and the 2012 Glover-Klingman prize.

Research topics

• Computer Science
• Physics
• Computer engineering
• Quantum mechanics
• Engineering
• Operating system

Selected publications

• Quantum Algorithms for Optimizers

  Society for Industrial and Applied Mathematics eBooks · 2025-12-17 · 1 citations

  book1st authorCorresponding
  PublisherDOI

• Introduction to the Special Issue on Quantum Computing and Operations Research

  INFORMS journal on computing · 2025-01-01 · 1 citations

  article
  PublisherDOI

• Quantum Optimization Benchmarking Library - The Intractable Decathlon

  ArXiv.org · 2025-04-04 · 2 citations

  preprintOpen access

  Through recent progress in hardware development, quantum computers have advanced to the point where benchmarking of (heuristic) quantum algorithms at scale is within reach. Particularly in combinatorial optimization - where most algorithms are heuristics - it is key to empirically analyze their performance on hardware and track progress towards quantum advantage. To this extent, we present ten optimization problem classes that are difficult for existing classical algorithms and can (mostly) be linked to practically relevant applications, with the goal to enable systematic, fair, and comparable benchmarks for quantum optimization methods. Further, we introduce the Quantum Optimization Benchmarking Library (QOBLIB) where the problem instances and solution track records can be found. The individual properties of the problem classes vary in terms of objective and variable type, coefficient ranges, and density. Crucially, they all become challenging for established classical methods already at system sizes ranging from less than 100 to, at most, an order of 100,000 decision variables, allowing to approach them with today's quantum computers. We reference the results from state-of-the-art solvers for instances from all problem classes and demonstrate exemplary baseline results obtained with quantum solvers for selected problems. The baseline results illustrate a standardized form to present benchmarking solutions, which has been designed to ensure comparability of the used methods, reproducibility of the respective results, and trackability of algorithmic and hardware improvements over time. We encourage the optimization community to explore the performance of available classical or quantum algorithms and hardware platforms with the benchmarking problem instances presented in this work toward demonstrating quantum advantage in optimization.

  PublisherOA PDFDOI

• Challenges and opportunities in quantum optimization

  Nature Reviews Physics · 2024-10-28 · 145 citations

  reviewOpen access
  PublisherOA PDFDOI

• Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits

  OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 2024-03-06 · 99 citations

  articleOpen access
  PublisherOA PDF

• Quantum algorithms for optimizers

  arXiv (Cornell University) · 2024-08-08

  preprintOpen access1st authorCorresponding

  This is a set of lecture notes for a graduate-level course on quantum algorithms, with an emphasis on quantum optimization algorithms. It is developed for applied mathematicians and engineers, and requires no previous background in quantum mechanics. The main topics of this course, in addition to a rigorous introduction to the computational model, are: input/output models, quantum search, the quantum gradient algorithm, matrix manipulation algorithms, the mirror descent framework for semidefinite optimization (including the matrix multiplicative weights update algorithm), adiabatic optimization. This is a preprint for personal use only. Please refer to the printed version of the material.

  PublisherOA PDFDOI

• Fully Polynomial Time Approximation Schemes for Robust Multistage Decision Making

  INFORMS journal on computing · 2024-12-11 · 1 citations

  articleSenior author

  We design a framework to obtain Fully Polynomial Time Approximation Schemes (FPTASes) for adjustable robust multistage decision making under the budgeted uncertainty sets introduced by Bertsimas and Sim. We apply this framework to the robust counterpart of three problems coming from operations research: (i) ordered knapsack, (ii) single-item inventory control, and (iii) single-item batch dispatch. Our work gives the first FPTAS for these problems, and for adjustable robust multistage decision making in general. The proposed approximation schemes are constructed with the technique of K-approximation sets and functions, relying on careful robust dynamic programming formulations for a master problem (corresponding to the decision maker) and for an adversary problem (corresponding to nature, which chooses bad realizations of uncertainty for the decision maker). The resulting algorithms are short and simple, requiring just a few concise subroutines. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research was supported in part by the United States-Israel Binational Science foundation [Grant 2018095). N. Halman was also supported in part by the Israel Science Foundation [Grants 399/17 and 1074/21].

  PublisherDOI

• A trust-region framework for derivative-free mixed-integer optimization

  Mathematical Programming Computation · 2024-08-24 · 1 citations

  article
  PublisherDOI

• A simple lower bound for the complexity of estimating partition functions on a quantum computer

  arXiv (Cornell University) · 2024-04-03

  preprintOpen accessSenior author

  We study the complexity of estimating the partition function $\mathsf{Z}(β)=\sum_{x\inχ} e^{-βH(x)}$ for a Gibbs distribution characterized by the Hamiltonian $H(x)$. We provide a simple and natural lower bound for quantum algorithms that solve this task by relying on reflections through the coherent encoding of Gibbs states. Our primary contribution is a $\varOmega(1/ε)$ lower bound for the number of reflections needed to estimate the partition function with a quantum algorithm. The proof is based on a reduction from the problem of estimating the Hamming weight of an unknown binary string.

  PublisherOA PDFDOI

• Special Issue: International Symposium on Mathematical Programming 2022

  Mathematical Programming · 2023-06-07

  articleOpen access

  This volume of MPB (Mathematical Programming, Series B) is dedicated to articles from the invited speakers of the 24th International Symposium on Mathematical Programming (ISMP).ISMP is the flagship conference of the Mathematical Optimization Society and has been held every three years since 1964.The Symposia have provided a comprehensive forum for presentation of research results in the mathematics of mathematical programming, in algorithms and computation, and in modeling.The latest conference was originally planned to be held in 2021 in Beijing but due to the pandemic it was first postponed for a year and then it was held online in 2022 with a small number of invited talks.The talks were scheduled and streamed one at a time at different times of the day in an effort to reach the worldwide MOS community.Each

  PublisherOA PDFDOI

Frequent coauthors

• Leo Liberti

  Laboratoire d'Informatique de l'École Polytechnique

  24 shared

• Emiliano Traversi

  Laboratoire d'Informatique de Paris-Nord

  16 shared

• Roberto Wolfler Calvo

  Université Sorbonne Paris Nord

  13 shared

• Oktay Günlük

  11 shared

• Nir Halman

  9 shared

• Brandon Augustino

  8 shared

• Lev S. Bishop

  8 shared

• Petar Jurcevic

  8 shared

Awards & honors

• 2021 Beale–Orchard-Hays
• 2021 IEEE QCE 2021 Best Paper Award
• 2016 COIN-OR Cup
• 2015 Robert Faure prize
• 2012 Glover-Klingman prize