8 Search Results for "Lee, Eunou"

Document
DOI: 10.4230/LIPIcs.ESA.2025.101
Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings

Authors: Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We introduce a 0.611-approximation algorithm for Quantum MaxCut and a (1+√5)/4 ≈ 0.809-approximation algorithm for the EPR Hamiltonian of [King, 2023]. A novel ingredient in both of these algorithms is to partially entangle pairs of qubits associated to edges in a matching, while preserving the direction of their single-qubit Bloch vectors. This allows us to interpolate between product states and matching-based states with a tunable parameter.
Cite as

Anuj Apte, Eunou Lee, Kunal Marwaha, Ojas Parekh, and James Sud. Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 101:1-101:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{apte_et_al:LIPIcs.ESA.2025.101,
  author =	{Apte, Anuj and Lee, Eunou and Marwaha, Kunal and Parekh, Ojas and Sud, James},
  title =	{{Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{101:1--101:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.101},
  URN =		{urn:nbn:de:0030-drops-245705},
  doi =		{10.4230/LIPIcs.ESA.2025.101},
  annote =	{Keywords: Quantum computing, Quantum MaxCut, Maximum matching}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.73
Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians

Authors: François Le Gall

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We construct classical algorithms computing an approximation of the ground state energy of an arbitrary k-local Hamiltonian acting on n qubits. We first consider the setting where a good "guiding state" is available, which is the main setting where quantum algorithms are expected to achieve an exponential speedup over classical methods. We show that a constant approximation (i.e., an approximation with constant relative accuracy) of the ground state energy can be computed classically in poly (1/χ,n) time and poly(n) space, where χ denotes the overlap between the guiding state and the ground state (as in prior works in dequantization, we assume sample-and-query access to the guiding state). This gives a significant improvement over the recent classical algorithm by Gharibian and Le Gall (SICOMP 2023), and matches (up to a polynomial overhead) both the time and space complexities of quantum algorithms for constant approximation of the ground state energy. We also obtain classical algorithms for higher-precision approximation. For the setting where no guided state is given (i.e., the standard version of the local Hamiltonian problem), we obtain a classical algorithm computing a constant approximation of the ground state energy in 2^O(n) time and poly(n) space. To our knowledge, before this work it was unknown how to classically achieve these bounds simultaneously, even for constant approximation. We also discuss complexity-theoretic aspects of our results.
Cite as

François Le Gall. Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 73:1-73:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{legall:LIPIcs.ESA.2025.73,
  author =	{Le Gall, Fran\c{c}ois},
  title =	{{Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{73:1--73:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.73},
  URN =		{urn:nbn:de:0030-drops-245419},
  doi =		{10.4230/LIPIcs.ESA.2025.73},
  annote =	{Keywords: approximation algorithms, quantum computing, dequantization}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.24
Improved Approximation Algorithms for the EPR Hamiltonian

Authors: Nathan Ju and Ansh Nagda

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

Abstract
The EPR Hamiltonian is a family of 2-local quantum Hamiltonians introduced by King [King, 2023]. We introduce a polynomial time (1+√5)/4≈0.809-approximation algorithm for the problem of computing the ground energy of the EPR Hamiltonian, improving upon the previous state of the art of 0.72 [Jorquera et al., 2024].
Cite as

Nathan Ju and Ansh Nagda. Improved Approximation Algorithms for the EPR Hamiltonian. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 24:1-24:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ju_et_al:LIPIcs.APPROX/RANDOM.2025.24,
  author =	{Ju, Nathan and Nagda, Ansh},
  title =	{{Improved Approximation Algorithms for the EPR Hamiltonian}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{24:1--24:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.24},
  URN =		{urn:nbn:de:0030-drops-243909},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.24},
  annote =	{Keywords: Approximation Algorithms, Quantum Local Hamiltonian}
}
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.105
An Improved Quantum Max Cut Approximation via Maximum Matching

Authors: Eunou Lee and Ojas Parekh

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Finding a high (or low) energy state of a given quantum Hamiltonian is a potential area to gain a provable and practical quantum advantage. A line of recent studies focuses on Quantum Max Cut, where one is asked to find a high energy state of a given antiferromagnetic Heisenberg Hamiltonian. In this work, we present a classical approximation algorithm for Quantum Max Cut that achieves an approximation ratio of 0.595, outperforming the previous best algorithms of Lee [Eunou Lee, 2022] (0.562, generic input graph) and King [King, 2023] (0.582, triangle-free input graph). The algorithm is based on finding the maximum weighted matching of an input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states of the previous best algorithms.
Cite as

Eunou Lee and Ojas Parekh. An Improved Quantum Max Cut Approximation via Maximum Matching. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 105:1-105:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.ICALP.2024.105,
  author =	{Lee, Eunou and Parekh, Ojas},
  title =	{{An Improved Quantum Max Cut Approximation via Maximum Matching}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{105:1--105:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.105},
  URN =		{urn:nbn:de:0030-drops-202482},
  doi =		{10.4230/LIPIcs.ICALP.2024.105},
  annote =	{Keywords: approximation, optimization, local Hamiltonian, rounding, SDP, matching}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.48
Optimizing Quantum Circuit Parameters via SDP

Authors: Eunou Lee

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
In recent years, parameterized quantum circuits have become a major tool to design quantum algorithms for optimization problems. The challenge in fully taking advantage of a given family of parameterized circuits lies in finding a good set of parameters in a non-convex landscape that can grow exponentially to the number of parameters. We introduce a new framework for optimizing parameterized quantum circuits: round SDP solutions to circuit parameters. Within this framework, we propose an algorithm that produces approximate solutions for a quantum optimization problem called Quantum Max Cut. The rounding algorithm runs in polynomial time to the number of parameters regardless of the underlying interaction graph. The resulting 0.562-approximation algorithm for generic instances of Quantum Max Cut improves on the previously known best algorithms by Anshu, Gosset, and Morenz with a ratio 0.531 and by Parekh and Thompson with a ratio 0.533.
Cite as

Eunou Lee. Optimizing Quantum Circuit Parameters via SDP. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lee:LIPIcs.ISAAC.2022.48,
  author =	{Lee, Eunou},
  title =	{{Optimizing Quantum Circuit Parameters via SDP}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{48:1--48:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.48},
  URN =		{urn:nbn:de:0030-drops-173330},
  doi =		{10.4230/LIPIcs.ISAAC.2022.48},
  annote =	{Keywords: Quantum algorithm, Optimization, Rounding algorithm, Quantum Circuit, Approximation}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.59
An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem

Authors: Sean Hallgren, Eunou Lee, and Ojas Parekh

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

Abstract
We present a classical approximation algorithm for the MAX-2-Local Hamiltonian problem. This is a maximization version of the QMA-complete 2-Local Hamiltonian problem in quantum computing, with the additional assumption that each local term is positive semidefinite. The MAX-2-Local Hamiltonian problem generalizes NP-hard constraint satisfaction problems, and our results may be viewed as generalizations of approximation approaches for the MAX-2-CSP problem. We work in the product state space and extend the framework of Goemans and Williamson for approximating MAX-2-CSPs. The key difference is that in the product state setting, a solution consists of a set of normalized 3-dimensional vectors rather than boolean numbers, and we leverage approximation results for rank-constrained Grothendieck inequalities. For MAX-2-Local Hamiltonian we achieve an approximation ratio of 0.328. This is the first example of an approximation algorithm beating the random quantum assignment ratio of 0.25 by a constant factor.
Cite as

Sean Hallgren, Eunou Lee, and Ojas Parekh. An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hallgren_et_al:LIPIcs.APPROX/RANDOM.2020.59,
  author =	{Hallgren, Sean and Lee, Eunou and Parekh, Ojas},
  title =	{{An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{59:1--59:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.59},
  URN =		{urn:nbn:de:0030-drops-126629},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.59},
  annote =	{Keywords: approximation algorithm, quantum computing, local Hamiltonian, mean-field theory, randomized rounding}
}
Document
DOI: 10.4230/LIPIcs.TQC.2020.7
Beyond Product State Approximations for a Quantum Analogue of Max Cut

Authors: Anurag Anshu, David Gosset, and Karen Morenz

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract
We consider a computational problem where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes Heisenberg interactions between qubits located at the vertices of a graph. Previous work has shed light on this problem’s approximability by product states. For any instance of this problem the maximum energy attained by a product state is lower bounded by the Max Cut of the graph and upper bounded by the standard Goemans-Williamson semidefinite programming relaxation of it. Gharibian and Parekh described an efficient classical approximation algorithm for this problem which outputs a product state with energy at least 0.498 times the maximum eigenvalue in the worst case, and observe that there exist instances where the best product state has energy 1/2 of optimal. We investigate approximation algorithms with performance exceeding this limitation which are based on optimizing over tensor products of few-qubit states and shallow quantum circuits. We provide an efficient classical algorithm which achieves an approximation ratio of at least 0.53 in the worst case. We also show that for any instance defined by a 3 or 4-regular graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state (larger even than its semidefinite programming relaxation).
Cite as

Anurag Anshu, David Gosset, and Karen Morenz. Beyond Product State Approximations for a Quantum Analogue of Max Cut. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{anshu_et_al:LIPIcs.TQC.2020.7,
  author =	{Anshu, Anurag and Gosset, David and Morenz, Karen},
  title =	{{Beyond Product State Approximations for a Quantum Analogue of Max Cut}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.7},
  URN =		{urn:nbn:de:0030-drops-120660},
  doi =		{10.4230/LIPIcs.TQC.2020.7},
  annote =	{Keywords: Approximation algorithms, Quantum many-body systems}
}
  • Refine by Type
  • 8 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2024
  • 1 2022
  • 2 2020

  • Refine by Author
  • 4 Lee, Eunou
  • 4 Parekh, Ojas
  • 1 Anshu, Anurag
  • 1 Apte, Anuj
  • 1 Gosset, David
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs

  • Refine by Classification
  • 5 Theory of computation → Approximation algorithms analysis
  • 2 Theory of computation → Quantum complexity theory
  • 1 Theory of computation
  • 1 Theory of computation → Quantum computation theory
  • 1 Theory of computation → Rounding techniques
  • Show More...

  • Refine by Keyword
  • 2 local Hamiltonian
  • 2 quantum computing
  • 1 Approximation
  • 1 Approximation Algorithms
  • 1 Approximation algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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