DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2026.4

Provable Speedups in Convex Optimization via Quantum Dynamics

Authors: Shouvanik Chakrabarti, Dylan Herman, Jacob Watkins, Enrico Fontana, Brandon Augustino, Junhyung Lyle Kim, and Marco Pistoia

Published in: LIPIcs, Volume 389, 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026)

Abstract

This work investigates the possibility of quantum speedups for continuous optimization through quantum Hamiltonian simulation. We establish the first rigorous query complexity bounds for unconstrained convex optimization via digital quantum annealing, based on the non-adiabatic Quantum Hamiltonian Descent (QHD) framework. In the process, we derive rigorous resource estimates for digital quantum simulation of Schrödinger operators depending only on input simulation parameters, given black-box evaluation access to separable, Lipschitz continuous potential b(t) f(x). We apply these simulation bounds to assess the complexity of high-dimensional convex optimization. Our annealing schedule achieves arbitrarily fast convergence rates in the evolution time, with computational time determined solely by the cost of discretization. We show that a G-Lipschitz convex function can be optimized to an error of ε with 𝒪̃(d^{1.5} G² R²/ε²) queries, given a starting point that is Euclidean distance R from optimal. Under reasonable assumptions such as the complexity of simulating Schrödinger operators, we show that Ω̃(d/ε²) queries are necessary. This suggests QHD does not offer improvements over classical methods in the noiseless zeroth order setting. However, we show that the QHD algorithm can tolerate 𝒪̃(ε³ /d^{1.5} G² R²) noise in function evaluation, and as a result, provides a super-quadratic query advantage over the best existing noise-tolerant classical algorithms in the high-dimensional setting. We leverage this to design a quantum algorithm for stochastic convex optimization that offers a super-quadratic speedup over all known classical and quantum algorithms in this regime. To our knowledge, these results represent the first rigorous quantum speedups for convex optimization obtained through a dynamical algorithm.

Cite as

Shouvanik Chakrabarti, Dylan Herman, Jacob Watkins, Enrico Fontana, Brandon Augustino, Junhyung Lyle Kim, and Marco Pistoia. Provable Speedups in Convex Optimization via Quantum Dynamics. In 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 389, pp. 4:1-4:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chakrabarti_et_al:LIPIcs.TQC.2026.4,
  author =	{Chakrabarti, Shouvanik and Herman, Dylan and Watkins, Jacob and Fontana, Enrico and Augustino, Brandon and Kim, Junhyung Lyle and Pistoia, Marco},
  title =	{{Provable Speedups in Convex Optimization via Quantum Dynamics}},
  booktitle =	{21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026)},
  pages =	{4:1--4:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-439-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{389},
  editor =	{Arnon, Rotem and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2026.4},
  URN =		{urn:nbn:de:0030-drops-273011},
  doi =		{10.4230/LIPIcs.TQC.2026.4},
  annote =	{Keywords: Convex optimization, Hamiltonian simulation, zeroth order}
}

Document

DOI: 10.4230/LIPIcs.ECOOP.2015.222

Access-rights Analysis in the Presence of Subjects

Authors: Paolina Centonze, Marco Pistoia, and Omer Tripp

Published in: LIPIcs, Volume 37, 29th European Conference on Object-Oriented Programming (ECOOP 2015)

Abstract

Modern software development and run-time environments, such as Java and the Microsoft .NET Common Language Runtime (CLR), have adopted a declarative form of access control. Permissions are granted to code providers, and during execution, the platform verifies compatibility between the permissions required by a security-sensitive operation and those granted to the executing code. While convenient, configuring the access-control policy of a program is not easy. If a code component is not granted sufficient permissions, authorization failures may occur. Thus, security administrators tend to define overly permissive policies, which violate the Principle of Least Privilege (PLP). A considerable body of research has been devoted to building program-analysis tools for computing the optimal policy for a program. However, Java and the CLR also allow executing code under the authority of a subject (user or service), and no program-analysis solution has addressed the challenges of determining the policy of a program in the presence of subjects. This paper introduces Subject Access Rights Analysis (SARA), a novel analysis algorithm for statically computing the permissions required by subjects at run time. We have applied SARA to 348 libraries in IBM WebSphere Application Server - a commercial enterprise application server written in Java that consists of >2 million lines of code and is required to support the Java permission- and subject-based security model. SARA detected 263 PLP violations, 219 cases of policies with missing permissions, and 29 bugs that led code to be unnecessarily executed under the authority of a subject. SARA corrected all these vulnerabilities automatically, and additionally synthesized fresh policies for all the libraries, with a false-positive rate of 5% and an average running time of 103 seconds per library. SARA also implements mechanisms for mitigating the risk of false negatives due to reflection and native code; according to a thorough result evaluation based on testing, no false negative was detected. SARA enabled IBM WebSphere Application Server to receive the Common Criteria for Information Technology Security Evaluation Assurance Level 4 certification.

Cite as

Paolina Centonze, Marco Pistoia, and Omer Tripp. Access-rights Analysis in the Presence of Subjects. In 29th European Conference on Object-Oriented Programming (ECOOP 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 37, pp. 222-246, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{centonze_et_al:LIPIcs.ECOOP.2015.222,
  author =	{Centonze, Paolina and Pistoia, Marco and Tripp, Omer},
  title =	{{Access-rights Analysis in the Presence of Subjects}},
  booktitle =	{29th European Conference on Object-Oriented Programming (ECOOP 2015)},
  pages =	{222--246},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-86-6},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{37},
  editor =	{Boyland, John Tang},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2015.222},
  URN =		{urn:nbn:de:0030-drops-52249},
  doi =		{10.4230/LIPIcs.ECOOP.2015.222},
  annote =	{Keywords: Static Analysis, Security, Access Control}
}

Search Results

Documents authored by Pistoia, Marco

Provable Speedups in Convex Optimization via Quantum Dynamics

Abstract

Cite as

Access-rights Analysis in the Presence of Subjects

Abstract

Cite as

Thanks for your feedback!

Could not send message