DROPS

Document

DOI: 10.4230/LIPIcs.TQC.2025.10

Hamiltonian Locality Testing via Trotterized Postselection

Authors: John Kallaugher and Daniel Liang

Published in: LIPIcs, Volume 350, 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)

Abstract

The (tolerant) Hamiltonian locality testing problem, introduced in [Bluhm, Caro, Oufkir '24], is to determine whether a Hamiltonian H is ε₁-close to being k-local (i.e. can be written as the sum of weight-k Pauli operators) or ε₂-far from any k-local Hamiltonian, given access to its time evolution operator and using as little total evolution time as possible, with distance typically defined by the normalized Frobenius norm. We give the tightest known bounds for this problem, proving an O(√(ε₂/((ε₂-ε₁)⁵)) evolution time upper bound and an Ω(1/(ε₂-ε₁)) lower bound. Our algorithm does not require reverse time evolution or controlled application of the time evolution operator, although our lower bound applies to algorithms using either tool. Furthermore, we show that if we are allowed reverse time evolution, this lower bound is tight, giving a matching O(1/(ε₂-ε₁)) evolution time algorithm.

Cite as

John Kallaugher and Daniel Liang. Hamiltonian Locality Testing via Trotterized Postselection. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kallaugher_et_al:LIPIcs.TQC.2025.10,
  author =	{Kallaugher, John and Liang, Daniel},
  title =	{{Hamiltonian Locality Testing via Trotterized Postselection}},
  booktitle =	{20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-392-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{350},
  editor =	{Fefferman, Bill},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2025.10},
  URN =		{urn:nbn:de:0030-drops-240593},
  doi =		{10.4230/LIPIcs.TQC.2025.10},
  annote =	{Keywords: quantum algorithms, property testing, hamiltonians}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2023.64

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

Authors: Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract

We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. Specifically, given an n-qubit pure state |ψ⟩, we give an efficient algorithm that distinguishes whether |ψ⟩ is (i) Haar-random or (ii) a state with stabilizer fidelity at least 1/k (i.e., has fidelity at least 1/k with some stabilizer state), promised that one of these is the case. With black-box access to |ψ⟩, our algorithm uses O(k^{12} log(1/δ)) copies of |ψ⟩ and O(n k^{12} log(1/δ)) time to succeed with probability at least 1-δ, and, with access to a state preparation unitary for |ψ⟩ (and its inverse), O(k³ log(1/δ)) queries and O(n k³ log(1/δ)) time suffice. As a corollary, we prove that ω(log(n)) T-gates are necessary for any Clifford+T circuit to prepare computationally pseudorandom quantum states, a first-of-its-kind lower bound.

Cite as

Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 64:1-64:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{grewal_et_al:LIPIcs.ITCS.2023.64,
  author =	{Grewal, Sabee and Iyer, Vishnu and Kretschmer, William and Liang, Daniel},
  title =	{{Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{64:1--64:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.64},
  URN =		{urn:nbn:de:0030-drops-175670},
  doi =		{10.4230/LIPIcs.ITCS.2023.64},
  annote =	{Keywords: Pseudorandom quantum states, Clifford + T, Haar random, Bell sampling, stabilizer formalism, stabilizer extent, stabilizer fidelity, learning theory, complexity theory}
}

Search Results

Documents authored by Liang, Daniel

Hamiltonian Locality Testing via Trotterized Postselection

Abstract

Cite as

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

Abstract

Cite as

Thanks for your feedback!

Could not send message