DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2021.49

Robust Quantum Entanglement at (Nearly) Room Temperature

Authors: Lior Eldar

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract

We formulate an average-case analog of the NLTS conjecture of Freedman and Hastings (QIC 2014) by asking whether there exist topologically ordered systems with corresponding local Hamiltonians for which the thermal Gibbs state for constant temperature cannot even be approximated by shallow quantum circuits. We then prove this conjecture for nearly optimal parameters: we construct a quantum error correcting code whose corresponding (log) local Hamiltonian has the following property: for nearly constant temperature (temperature decays as 1/log²log(n)) the thermal Gibbs state of that Hamiltonian cannot be approximated by any circuit of depth less than log(n), and it is highly entangled in a well-defined way. This implies that appropriately chosen local Hamiltonians can give rise to ground-state long-range entanglement which can survive without active error correction at temperatures which are nearly independent of the system size: thereby improving exponentially upon previously known bounds.

Cite as

Lior Eldar. Robust Quantum Entanglement at (Nearly) Room Temperature. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 49:1-49:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{eldar:LIPIcs.ITCS.2021.49,
  author =	{Eldar, Lior},
  title =	{{Robust Quantum Entanglement at (Nearly) Room Temperature}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{49:1--49:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.49},
  URN =		{urn:nbn:de:0030-drops-135886},
  doi =		{10.4230/LIPIcs.ITCS.2021.49},
  annote =	{Keywords: Quantum error-correcting codes, Quantum Entanglement, Quantum Locally-Testable Codes, Local Hamiltonians, quantum PCP, NLTS}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2018.6

A Quasi-Random Approach to Matrix Spectral Analysis

Authors: Michael Ben-Or and Lior Eldar

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract

Inspired by quantum computing algorithms for Linear Algebra problems [Harrow et al., Phys. Rev. Lett. 2009, Ta-Shma, STOC 2013] we study how simulation on a classical computer of this type of "Phase Estimation algorithms" performs when we apply it to the Eigen-Problem of Hermitian matrices. The result is a completely new, efficient and stable, parallel algorithm to compute an approximate spectral decomposition of any Hermitian matrix. The algorithm can be implemented by Boolean circuits in O(log^2(n)) parallel time with a total cost of O(n^(\omega+1)) Boolean operations. This Boolean complexity matches the best known O(log^2(n)) parallel time algorithms, but unlike those algorithms our algorithm is (logarithmically) stable, so it may lead to actual implementations, allowing fast parallel computation of eigenvectors and eigenvalues in practice. Previous approaches to solve the Eigen-Problem generally use randomization to avoid bad conditions - as we do. Our algorithm makes further use of randomization in a completely new way, taking random powers of a unitary matrix to randomize the phases of its eigenvalues. Proving that a tiny Gaussian perturbation and a random polynomial power are sufficient to ensure almost pairwise independence of the phases (mod 2pi) is the main technical contribution of this work. It relies on the theory of low-discrepancy or quasi-random sequences - a theory, which to the best of our knowledge, has not been connected thus far to linear algebra problems. Hence, we believe that further study of this new connection will lead to additional improvements.

Cite as

Michael Ben-Or and Lior Eldar. A Quasi-Random Approach to Matrix Spectral Analysis. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 6:1-6:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{benor_et_al:LIPIcs.ITCS.2018.6,
  author =	{Ben-Or, Michael and Eldar, Lior},
  title =	{{A Quasi-Random Approach to Matrix Spectral Analysis}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{6:1--6:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.6},
  URN =		{urn:nbn:de:0030-drops-83288},
  doi =		{10.4230/LIPIcs.ITCS.2018.6},
  annote =	{Keywords: linear algebra, eigenvalues, eigenvectors, low-discrepancy sequence}
}

Search Results

Documents authored by Eldar, Lior

Robust Quantum Entanglement at (Nearly) Room Temperature

Abstract

Cite as

A Quasi-Random Approach to Matrix Spectral Analysis

Abstract

Cite as

Thanks for your feedback!

Could not send message