Search Results

Documents authored by Kallaugher, John

Document
DOI: 10.4230/LIPIcs.ITCS.2025.63
Complexity Classification of Product State Problems for Local Hamiltonians

Authors: John Kallaugher, Ojas Parekh, Kevin Thompson, Yipu Wang, and Justin Yirka

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
Product states, unentangled tensor products of single qubits, are a ubiquitous ansatz in quantum computation, including for state-of-the-art Hamiltonian approximation algorithms. A natural question is whether we should expect to efficiently solve product state problems on any interesting families of Hamiltonians. We completely classify the complexity of finding minimum-energy product states for Hamiltonians defined by any fixed set of allowed 2-qubit interactions. Our results follow a line of work classifying the complexity of solving Hamiltonian problems and classical constraint satisfaction problems based on the allowed constraints. We prove that estimating the minimum energy of a product state is in 𝖯 if and only if all allowed interactions are 1-local, and NP-complete otherwise. Equivalently, any family of non-trivial two-body interactions generates Hamiltonians with NP-complete product-state problems. Our hardness constructions only require coupling strengths of constant magnitude. A crucial component of our proofs is a collection of hardness results for a new variant of the Vector Max-Cut problem, which should be of independent interest. Our definition involves sums of distances rather than squared distances and allows linear stretches. We similarly give a proof that the original Vector Max-Cut problem is NP-complete in 3 dimensions. This implies hardness of optimizing product states for Quantum Max-Cut (the quantum Heisenberg model) is NP-complete, even when every term is guaranteed to have positive unit weight.
Cite as

John Kallaugher, Ojas Parekh, Kevin Thompson, Yipu Wang, and Justin Yirka. Complexity Classification of Product State Problems for Local Hamiltonians. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 63:1-63:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kallaugher_et_al:LIPIcs.ITCS.2025.63,
  author =	{Kallaugher, John and Parekh, Ojas and Thompson, Kevin and Wang, Yipu and Yirka, Justin},
  title =	{{Complexity Classification of Product State Problems for Local Hamiltonians}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{63:1--63:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.63},
  URN =		{urn:nbn:de:0030-drops-226910},
  doi =		{10.4230/LIPIcs.ITCS.2025.63},
  annote =	{Keywords: quantum complexity, quantum algorithms, local hamiltonians}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.11
An Optimal Algorithm for Triangle Counting in the Stream

Authors: Rajesh Jayaram and John Kallaugher

Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

Abstract
We present a new algorithm for approximating the number of triangles in a graph G whose edges arrive as an arbitrary order stream. If m is the number of edges in G, T the number of triangles, Δ_E the maximum number of triangles which share a single edge, and Δ_V the maximum number of triangles which share a single vertex, then our algorithm requires space: Õ(m/T⋅(Δ_E + √{Δ_V})) Taken with the Ω((m Δ_E)/T) lower bound of Braverman, Ostrovsky, and Vilenchik (ICALP 2013), and the Ω((m √{Δ_V})/T) lower bound of Kallaugher and Price (SODA 2017), our algorithm is optimal up to log factors, resolving the complexity of a classic problem in graph streaming.
Cite as

Rajesh Jayaram and John Kallaugher. An Optimal Algorithm for Triangle Counting in the Stream. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 11:1-11:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jayaram_et_al:LIPIcs.APPROX/RANDOM.2021.11,
  author =	{Jayaram, Rajesh and Kallaugher, John},
  title =	{{An Optimal Algorithm for Triangle Counting in the Stream}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{11:1--11:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.11},
  URN =		{urn:nbn:de:0030-drops-147046},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.11},
  annote =	{Keywords: Triangle Counting, Streaming, Graph Algorithms, Sampling, Sketching}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact