3 Search Results for "Gosset, David"

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-dev.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}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.31
Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut

Authors: Sevag Gharibian and Ojas Parekh

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

Abstract
Approximation algorithms for constraint satisfaction problems (CSPs) are a central direction of study in theoretical computer science. In this work, we study classical product state approximation algorithms for a physically motivated quantum generalization of Max-Cut, known as the quantum Heisenberg model. This model is notoriously difficult to solve exactly, even on bipartite graphs, in stark contrast to the classical setting of Max-Cut. Here we show, for any interaction graph, how to classically and efficiently obtain approximation ratios 0.649 (anti-feromagnetic XY model) and 0.498 (anti-ferromagnetic Heisenberg XYZ model). These are almost optimal; we show that the best possible ratios achievable by a product state for these models is 2/3 and 1/2, respectively.
Cite as

Sevag Gharibian and Ojas Parekh. Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gharibian_et_al:LIPIcs.APPROX-RANDOM.2019.31,
  author =	{Gharibian, Sevag and Parekh, Ojas},
  title =	{{Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{31:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.31},
  URN =		{urn:nbn:de:0030-drops-112463},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.31},
  annote =	{Keywords: Approximation algorithm, Max-Cut, local Hamiltonian, QMA-hard, Heisenberg model, product state}
}
Document
DOI: 10.4230/LIPIcs.TQC.2019.8
A Compressed Classical Description of Quantum States

Authors: David Gosset and John Smolin

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
We show how to approximately represent a quantum state using the square root of the usual amount of classical memory. The classical representation of an n-qubit state psi consists of its inner products with O(sqrt{2^n}) stabilizer states. A quantum state initially specified by its 2^n entries in the computational basis can be compressed to this form in time O(2^n poly(n)), and, subsequently, the compressed description can be used to additively approximate the expectation value of an arbitrary observable. Our compression scheme directly gives a new protocol for the vector in subspace problem with randomized one-way communication complexity that matches (up to polylogarithmic factors) the optimal upper bound, due to Raz. We obtain an exponential improvement over Raz’s protocol in terms of computational efficiency.
Cite as

David Gosset and John Smolin. A Compressed Classical Description of Quantum States. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 8:1-8:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gosset_et_al:LIPIcs.TQC.2019.8,
  author =	{Gosset, David and Smolin, John},
  title =	{{A Compressed Classical Description of Quantum States}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{8:1--8:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.8},
  URN =		{urn:nbn:de:0030-drops-104005},
  doi =		{10.4230/LIPIcs.TQC.2019.8},
  annote =	{Keywords: Quantum computation, Quantum communication complexity, Classical simulation}
}
  • Refine by Author
  • 2 Gosset, David
  • 1 Anshu, Anurag
  • 1 Gharibian, Sevag
  • 1 Morenz, Karen
  • 1 Parekh, Ojas
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Quantum complexity theory
  • 1 Theory of computation
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Quantum computation theory
  • 1 Theory of computation → Semidefinite programming

  • Refine by Keyword
  • 1 Approximation algorithm
  • 1 Approximation algorithms
  • 1 Classical simulation
  • 1 Heisenberg model
  • 1 Max-Cut
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2019
  • 1 2020

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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact