Hamiltonian Locality Testing via Trotterized Postselection

Daniel Liang; John Kallaugher

REVIEW 3 major objections 3 minor 2 cited by

Hamiltonian Locality Testing via Trotterized Postselection

T0 review · 3 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper nearly closes the complexity of Hamiltonian locality testing, with near-optimal forward-only bounds and a Heisenberg-limited algorithm when reverse evolution is allowed.

desk verdict Forward-only tester and lower bound are solid; the matching reverse-evolution bound rests on a false lemma and needs repair. read the letter →

arxiv 2505.06478 v1 pith:BU7E3BA4 submitted 2025-05-10 quant-ph cs.CCcs.DS

John Kallaugher , Daniel Liang This is my paper · ORCID

classification quant-phcs.CCcs.DS MSC 81P6868Q12

keywords HamiltonianlocalitytestingtolerantpropertyquantumquerycomplexityTrotterizedpostselectiontimeevolutionoracleBellbasissamplingk-localHeisenberglimit

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies Hamiltonian locality testing: decide whether an $n$-qubit Hamiltonian $H$ is $\varepsilon_1$-close to a $k$-local Hamiltonian or $\varepsilon_2$-far from all such, given access to the evolution operator $e^{-iHt}$, with cost measured by total evolution time. It establishes three results: a forward-only, non-adaptive algorithm using $O(\sqrt{\varepsilon_2/(\varepsilon_2-\varepsilon_1)^5}\,\log(1/\delta))$ total evolution time; a lower bound $\Omega(1/(\varepsilon_2-\varepsilon_1))$ that holds even for algorithms with reverse or controlled queries; and, when reverse evolution is allowed, a matching $O(\log(1/\delta)/(\varepsilon_2-\varepsilon_1))$ algorithm. The engine is a new technique, Trotterized postselection, which simulates evolution under only the non-local part of $H$ by repeatedly evolving for a short time and postselecting on the subspace of non-local (or identity) Bell states. If correct, the reverse-query version makes the tolerant locality testing problem Heisenberg-limited, and the lower bound identifies the tolerance gap $\varepsilon_2-\varepsilon_1$ as the fundamental resource.

What carries the argument

Trotterized postselection. Starting from the maximally entangled Bell state $|\sigma_{I^{\otimes n}}\rangle$, the algorithm repeatedly applies $I\otimes e^{-i\alpha H}$ for a small step $\alpha$ and measures the projector $\Pi_D$ onto the subspace spanned by identity and non-local Pauli Bell states, postselecting on success. The effective map per step is $e^{-i\alpha A}+O(\alpha^2)$ with $A=\Pi_D(I\otimes H)\Pi_D$; because the identity (trace) component of $H$ has been removed, $A|\sigma_{I^{\otimes n}}\rangle=(I\otimes H_{>k})|\sigma_{I^{\otimes n}}\rangle$, so $\langle\sigma_I|A^2|\sigma_I\rangle=\|H_{>k}\|_2^2$ is exactly the squared distance to $k$-locality. This suppresses the higher-order Taylor terms that forced earlier algorithms to use step size $t\approx\varepsilon$, allowing $t=\Theta(\sqrt{\varepsilon_2^2-\varepsilon_1^2}/\varepsilon_2)$ and yielding the improved query count.

What would settle it

Set $\varepsilon_1=0$, take $H$ to be exactly $k$-local with $\|H\|_\infty=1$, and compute $\|U_{>k}\|_2^2$ for any step $\alpha$: the exact value is $0$. The lemma quoted from [ADG24] in the proof of Theorem 4 asserts a strictly positive upper bound in this setting, so the printed lemma is false; checking whether a corrected lemma still yields the $O(1/\Delta)$ query count settles the matching-upper-bound claim.

Watch

Extended reading notes

Core claim

The central claim is that the tolerance gap $\Delta=\varepsilon_2-\varepsilon_1$, not the distance scale $\varepsilon_2$, controls the cost of Hamiltonian locality testing. Concretely, Theorem 1 gives an $O(\sqrt{\varepsilon_2/\Delta^5}\,\log(1/\delta))$-time algorithm requiring only forward evolutions and no controlled gates, and Theorem 2 shows any algorithm, even with reverse or controlled access, needs $\Omega(1/\Delta)$ evolution time. Theorem 4 then closes the gap when reverse evolution is available: amplitude estimation on the step-$\alpha$ propagator yields an $O(\log(1/\delta)/\Delta)$-time tester, so the problem is Heisenberg-limited in $\Delta$. The technical core is that the $O(\alpha^2)$ error per step of the postselected evolution against $e^{-iAt}$ (where $A=\Pi_D(I\otimes H)\Pi_D$) accumulates only to $O(\alpha t)$, because the postselection succeeds with high probability in each small step.

Load-bearing premise

The reverse-query optimal algorithm rests on a quoted lemma from [ADG24] whose stated bound is inconsistent at $\varepsilon_1=0$, and separately on a trace-free simplification that is only valid without controlled queries, while Theorem 4 uses controlled applications where the global phase can be observed.

Editorial extensions

If this is right

Any tester for the tolerant locality gap must use $\Omega(1/(\varepsilon_2-\varepsilon_1))$ total evolution time, even when reverse or controlled queries are available.
With forward-only queries, the paper's algorithm achieves the best known scaling, $O(\sqrt{\varepsilon_2/(\varepsilon_2-\varepsilon_1)^5}\,\log(1/\delta))$ total evolution time, using non-adaptive queries and $n$ ancilla qubits.
With reverse evolution allowed, the $O(\log(1/\delta)/(\varepsilon_2-\varepsilon_1))$ algorithm matches the lower bound, making the tolerant problem Heisenberg-limited in the gap.
The lower bound is witness-robust: it holds for normalized Frobenius distance and, by the same diagonal witness $\varepsilon Z_{1:k}$, also for operator norm, normalized Schatten $p$-norms, and Pauli decomposition $p$-norms.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The postselection idea should transfer to other Hamiltonian properties defined by dropping Pauli terms, such as bounded interaction graph or limited Pauli weight, and may yield Heisenberg-limited testers there too.
The trace-free step is only valid without controlled queries, so the reverse-query algorithm has an unaccounted phase issue: either the controlled amplitude-estimation calls observe the global phase and break the reduction, or the algorithm needs a phase-tracking variant.
The frontier left open is the forward-only complexity: between the $\Omega(1/\Delta)$ lower bound and the $O(\sqrt{\varepsilon_2/\Delta^5})$ upper bound there is a substantial gap, and closing it likely needs a genuinely different technique than postselection.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know. The forward-only tester (Theorem 1) and the lower bound (Theorem 2) are solid and well argued; the Trotterized postselection idea genuinely beats the Taylor-series barrier, and the lower bound via diamond distance between ε1Z and ε2Z is clean. The matching reverse-evolution algorithm (Theorem 4) is not supported as written, because the key Lemma 24 quoted from ADG24 is false.

Here is the concrete failure. Take H=Z1Z2, k=1, ε2=1, ε1=1−δ, α=(ε2−ε1)/(3c). Then U=e^{-iHα} has nonlocal weight-2 component sin²α ≈ δ²/(9c²). Lemma 24's far-case lower bound is ((δ(1−δ)+2)/(9c))² ≈ 4/(81c²), a constant independent of δ. For δ=10⁻⁴ the two differ by six orders of magnitude. So the separation Theorem 4 relies on is not established. The reader's ε1=0 objection is not the right one: powers of a local H do generate nonlocal components of e^{-iHα}, so the close-case upper bound being nonzero is not itself a bug. The real bug is the far-case bound's independence from the gap.

There is a second gap in Theorem 4: Section 3.1 assumes Tr(H)=0 WLOG because a global phase is unobservable, but that is only true without controlled applications. Theorem 4 explicitly uses controlled U and U† for amplitude estimation, where the phase matters. Probably fixable, but not fixed.

None of this undermines Theorems 1 and 2. The analysis there (Lemmas 13, 14, 17, 18) is detailed and looks internally consistent, with a query/time tradeoff that beats the previous O(gap⁻³) and O(gap⁻²·⁵ ε₂⁻⁰·⁵) bounds. The lower bound is genuinely the first for arbitrary ε in the tolerant setting, and it covers controlled and reverse access. Citation pattern is fine; the [GIKL23] self-citation is backed by standard amplitude estimation.

Who is this for: people working on Hamiltonian locality testing, quantum property testing, and Heisenberg-limited Hamiltonian learning. It deserves a serious referee. I would send it to review and ask the referee to scrutinize Theorem 4; if the authors cannot repair it, the matching claim should be withdrawn, but Theorems 1 and 2 should stand.

Referee Report

3 major / 3 minor

Summary. The paper studies tolerant Hamiltonian locality testing: given query access to the time evolution operator e^{-iHt}, decide whether H is ε1-close to a k-local Hamiltonian or ε2-far from every k-local Hamiltonian, with distance measured by normalized Frobenius norm. The main results are Theorem 1, a forward-only, non-adaptive algorithm using O(sqrt(ε2/(ε2-ε1)^5 log(1/δ))) total evolution time and O(sqrt(ε2/(ε2-ε1)^7 log(1/δ))) queries; Theorem 2, an Ω(1/(ε2-ε1)) evolution-time lower bound that also applies to algorithms with reverse or controlled access; and Theorem 4, a matching O(1/(ε2-ε1)) algorithm when reverse evolution and controlled operations are allowed. The upper bound is obtained by a Trotterized postselection procedure that approximately implements the evolution of the nonlocal part H_{>k} of the Hamiltonian, while the lower bound uses a pair of commuting Hamiltonians whose time evolutions are close in diamond distance. Theorem 4 uses amplitude estimation on the nonlocal component of e^{-iHα} with a step size α proportional to ε2-ε1.

Significance. If Theorems 1 and 2 are correct, the paper gives the tightest known bounds for Hamiltonian locality testing in the tolerant setting, improves the previous evolution-time upper bounds, and supplies the first lower bound that works for arbitrary ε1, ε2. The forward-only algorithm is notable because it avoids reverse evolution and controlled oracle access, and the proof is built from explicit, mostly self-contained lemmas. Theorem 4 would close the problem by showing that the lower bound is tight when inverse queries are available. However, the proof of Theorem 4 depends on a quoted lemma that is false as stated, so that part of the paper's central claim is currently unsupported. The main forward-only upper bound and the lower bound appear structurally sound and are the paper's strongest contribution.

major comments (3)

[Appendix A, Lemma 24] Lemma 24 is false as stated, and Theorem 4's proof collapses with it. Take k=1, H=Z1Z2 so that ||H||∞=1, let ε2=1, ε1=1-δ, and let c be any fixed constant. Then α=(ε2-ε1)/(3c)=δ/(3c), and U=e^{-iHα}=cos(α)I - i sin(α)Z1Z2. Since H has only the identity and the weight-2 Pauli Z1Z2, the projected component U_{>1} has squared norm ||U_{>1}||₂²=sin²(α)≈δ²/(9c²). Lemma 24's lower bound for the ε2-far case is ((δ(1-δ)+2)/(9c))²≈4/(81c²), which is independent of δ. For δ=10^{-4} and c=1, the true value is about 1.23×10^{-8} while the lemma's lower bound is about 4.95×10^{-2}. Thus the claimed separation between the close and far cases, and hence the query and time bounds derived from it in the proof of Theorem 4, is not established. A corrected lemma would need the projected norm to depend on (ε2-ε1)², not on a constant; the proof of Theorem 4 must be reworked or the theorem withdrawn.
[Section 4.1, Algorithm 1 and definitions] The number of postselection iterations is stated inconsistently. The text defines α=(ε2²-ε1²)/(100ε2), t=sqrt(ε2²-ε1²)/(2ε2), and then claims m:=t/α=50√(ε2²-ε1²). But t/α = [sqrt(Δ)/(2ε2)]·[100ε2/Δ] = 50/√Δ, where Δ=ε2²-ε1². Algorithm 1's loop is also written as 'for 50√ε2²-ε1² iterations'. With the stated m=50√Δ, the total evolution time would be mα=Δ^{3/2}/(2ε2), contradicting the definition t=√Δ/(2ε2) and invalidating the error bounds in Lemmas 14 and 18. The later query-count algebra in Theorem 1, which produces a Δ^{-7/2} dependence, is consistent only with m=50/√Δ. This appears to be a typo, but it must be corrected in both the algorithm statement and the definition of m, since the algorithm as printed does not implement the analyzed procedure.
[Section 3.1] The trace-free assumption Tr(H)=0 is justified only for algorithms that do not use controlled applications of the time evolution operator, yet Theorem 4 and its proof use controlled operations through the amplitude-estimation subroutine. The manuscript should either restrict the WLOG to the uncontrolled algorithms or provide the missing justification for the controlled setting. The issue is likely fixable: the reflection R_ψ used in Lemma 25 is phase-invariant, and the implementation via U and U† applies the global phase in conjugate pairs, so the identity component of H may cancel. But this needs to be stated explicitly, because as written the WLOG in Section 3.1 does not cover the algorithm in Appendix A.

minor comments (3)

[Lemma 21] The statement of Lemma 21 writes the diamond-distance bound as 2(ε1-ε2)t, which is negative for ε1<ε2; it should be 2|ε1-ε2|t or 2(ε2-ε1)t. The proof's final inequality correctly uses (ε2-ε1)t.
[Theorem 1 proof] In the query-count display near the end of the proof of Theorem 1, the exponent 7/2 in the denominator is correct only after the iteration count m is corrected to 50/√(ε2²-ε1²). As printed, with m=50√(ε2²-ε1²), the algebraic step from s′m to the Δ^{-7/2} bound is incorrect. This should be fixed together with the m definition in Section 4.1.
[Appendix A, Lemma 25] The statement of Lemma 25 says the algorithm makes calls to controlled versions of RΠ and R_ψ, but the proof then says R_ψ is implemented by conjugating the Grover diffusion operator by U and U†. It would help to spell out how controlled-R_ψ is obtained from controlled or uncontrolled U and U†, especially because the controlled-U oracle may include a global phase when H is not trace-free.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central bounds are derived from explicit in-paper lemmas or independently grounded external tools.

full rationale

The paper's main upper bound (Theorem 1) is proven by an explicit analysis of Algorithm 1: Lemma 13 bounds the Trotterized-postselection step against e^{-iAalpha}, Lemma 14 controls the accumulated error and normalization, Lemmas 16 and 17 relate the estimator's expectation to ||H_{>k}||_2^2, and Theorem 1 then concentrates the Bernoulli samples. None of these steps uses the theorem being proved, or a quantity defined in terms of the target separation, as an input; the algorithm's step size and threshold are chosen from epsilon1 and epsilon2 only after the estimator's expectation is derived. The lower bound (Theorem 2) is a direct diamond-distance argument on the explicit pair H1 = epsilon1 Z_{1:k'} and H2 = epsilon2 Z_{1:k'}, using Lemma 21 and subadditivity; it does not presuppose the lower bound. Theorem 4 builds on the quoted [ADG24, Lemma 3.1] and on [GIKL23, Corollary 29], but neither citation is a self-citation chain that forces the conclusion: [ADG24] is by non-overlapping authors, and [GIKL23] is itself presented as a corollary of the external Quantum Amplitude Estimation theorem [BHMT02, Theorem 12], with stated assumptions that do not include the target result. The skeptical observation that [ADG24, Lemma 3.1] may be quantitatively incorrect is a correctness concern about an imported lemma, not a demonstration that the paper's derivation is circular: the derivation is independent of whether that lemma is true. Likewise, the trace-free WLOG in Section 3.1 is stated for algorithms that do not use controlled application of the unitary, while Theorem 4 uses controlled applications; this is a flagged support gap, not a case of the conclusion being assumed in the premise. The appendix also notes that using the multiplicative error form from [VO21] could remove the need for controlled access, which is a limitation note rather than a circular step. Accordingly, no circular step meeting the quoted-equation reduction standard was found.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

No empirical free parameters are used; the algorithm constants are explicit functions of epsilon1 and epsilon2. The proof relies on standard quantum information tools plus one external lemma from ADG24 whose transcription appears corrupted. The trace-free WLOG is flagged because it is only justified in the uncontrolled setting but is reused in the controlled Appendix.

free parameters (3)

Trotterized postselection step size alpha = (epsilon2^2 - epsilon1^2) / (100 epsilon2)
Chosen by hand to keep per-step error O(alpha^2); any sufficiently small alpha works, so it is not fitted to data.
Total per-run evolution time t = sqrt(epsilon2^2 - epsilon1^2) / (2 epsilon2)
Set by the theorem to balance signal epsilon^2 t^2 against Taylor error; explicit function of problem parameters, not a data fit.
Number of postselection iterations m = 50 sqrt(epsilon2^2 - epsilon1^2)
Equals t/alpha; algorithmic design choice, not fitted to data.

assumptions (6)

standard math Pauli matrices form an orthogonal basis under the normalized Frobenius inner product; Bell basis sampling reads the Pauli spectrum of a unitary.
Used throughout Section 3.1 and in the algorithm analysis; standard result from [MO10].
domain assumption Hamiltonian normalization: ||H||_infinity <= 1 and Tr(H)=0 WLOG.
Section 3.1; normalization is standard in the literature, trace-free WLOG is valid for uncontrolled queries but is not justified for Theorem 4.
domain assumption Time evolution oracle is exactly e^{-iHt}, and cost is total evolution time, with arbitrary ancillas and measurements allowed.
Problem definition inherited from [BCO24].
standard math Diamond distance sub-additivity and the standard distinguishability bound for quantum channels.
Used in Section 5 for the lower bound; standard from [Wil17].
domain assumption [ADG24, Lemma 3.1]: first-order separation of U_{>k} for epsilon1-close versus epsilon2-far Hamiltonians.
Quoted in Appendix A with apparent notation corruption; load-bearing for Theorem 4.
standard math Quantum amplitude estimation can estimate eta to accuracy zeta with O(sqrt(eta(1-eta))/zeta) controlled queries.
Used in Theorem 4; sourced from [BHMT02] via [GIKL23, Corollary 29].

how reviews work

0 comments

Cite this review

Pith. "Pith review of Hamiltonian Locality Testing via Trotterized Postselection." pith.science (2026). https://pith.science/paper/BU7E3BA4

@misc{pith2026250506478,
  author       = {Pith},
  title        = {Pith review of: Hamiltonian Locality Testing via Trotterized Postselection},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BU7E3BA4}},
  note         = {Machine review of arXiv:2505.06478}
}

abstract

The (tolerant) Hamiltonian locality testing problem, introduced in [Bluhm, Caro,Oufkir `24], is to determine whether a Hamiltonian $H$ is $\varepsilon_1$-close to being $k$-local (i.e. can be written as the sum of weight-$k$ Pauli operators) or $\varepsilon_2$-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 $\text{O}\left(\sqrt{\frac{\varepsilon_2}{(\varepsilon_2-\varepsilon_1)^5}}\right)$ evolution time upper bound and an $\Omega\left(\frac{1}{\varepsilon_2-\varepsilon_1}\right)$ 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 $\text{O}\left(\frac{1}{\varepsilon_2-\varepsilon_1}\right)$ evolution time algorithm.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Certifying and learning quantum Ising Hamiltonians
quant-ph 2025-09 conditional novelty 7.0 of 10

Near-optimal certification of quantum Ising Hamiltonians from time evolution, plus sample-efficient learning and certification of their Gibbs states.
Improved Hamiltonian learning and sparsity testing through Bell sampling
quant-ph 2025-09 conditional novelty 6.0 of 10

A refined Bell-sampling analysis reduces sparse Hamiltonian learning to near-linear evolution time and produces a faster Hamiltonian sparsity test, both using only forward time evolution.

Reference graph

Works this paper leans on

21 extracted references · 5 canonical work pages · cited by 2 Pith papers

[1]

Sample-efficient learning of interacting quantum systems

Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahar, and Mehdi Soleimanifar. Sample-efficient learning of interacting quantum systems. Nature Physics , 17:931--935, Aug 2021. https://doi.org/10.1038/s41567-021-01232-0 doi:10.1038/s41567-021-01232-0

doi:10.1038/s41567-021-01232-0 2021
[2]

The Quantum PCP Conjecture

Dorit Aharonov, Itai Arad, and Thomas Vidick. The quantum PCP conjecture, 2013. http://arxiv.org/abs/1309.7495 arXiv:1309.7495

work page Pith review arXiv 2013
[3]

Testing and learning structured quantum hamiltonians, 2024

Srinivasan Arunachalam, Arkopal Dutt, and Francisco Escudero Gutiérrez. Testing and learning structured quantum hamiltonians, 2024. http://arxiv.org/abs/2411.00082 arXiv:2411.00082

arXiv 2024
[4]

Caro, and Aadil Oufkir

Andreas Bluhm, Matthias C. Caro, and Aadil Oufkir. Hamiltonian Property Testing , 2024. http://arxiv.org/abs/2403.02968 arXiv:2403.02968

arXiv 2024
[5]

Quantum Amplitude Amplification and Estimation , 2002

Gilles Brassard, Peter H yer, Michele Mosca, and Alain Tapp. Quantum Amplitude Amplification and Estimation , 2002. https://doi.org/10.1090/conm/305/05215 doi:10.1090/conm/305/05215

doi:10.1090/conm/305/05215 2002
[6]

Learning quantum hamiltonians at any temperature in polynomial time

Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang. Learning quantum hamiltonians at any temperature in polynomial time. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , STOC 2024, page 1470–1477, New York, NY, USA, 2024. Association for Computing Machinery. https://doi.org/10.1145/3618260.3649619 doi:10.1145/3618260.3649619

arXiv 2024
[7]

Structure learning of hamiltonians from real-time evolution

Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang. Structure learning of hamiltonians from real-time evolution. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1037--1050, 2024. https://doi.org/10.1109/FOCS61266.2024.00069 doi:10.1109/FOCS61266.2024.00069

arXiv 2024
[8]

Childs, Dmitri Maslov, Yunseong Nam, Neil J

Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su. Toward the first quantum simulation with quantum speedup. Proceedings of the National Academy of Sciences , 115(38):9456--9461, 2018. https://doi.org/10.1073/pnas.1801723115 doi:10.1073/pnas.1801723115

doi:10.1073/pnas.1801723115 2018

Show all 21 references

[9]

Elitzur and Lev Vaidman

Avshalom C. Elitzur and Lev Vaidman. Quantum mechanical interaction-free measurements. Foundations of Physics , 23:987--997, 1993. https://doi.org/10.1007/BF00736012 doi:10.1007/BF00736012

1993 doi
[10]

Quantum zeno dynamics: mathematical and physical aspects

P Facchi and S Pascazio. Quantum zeno dynamics: mathematical and physical aspects. Journal of Physics A: Mathematical and Theoretical , 41(49):493001, oct 2008. https://doi.org/10.1088/1751-8113/41/49/493001 doi:10.1088/1751-8113/41/49/493001

2008 doi
[11]

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom . In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , volume 251 of Leibniz International Proceedi...

2023 doi
[12]

Simple algorithms to test and learn local Hamiltonians , 2024

Francisco Escudero Gutiérrez. Simple algorithms to test and learn local Hamiltonians , 2024. http://arxiv.org/abs/2404.06282 arXiv:2404.06282

2024 arXiv
[13]

J. Haah, R. Kothari, R. O'Donnell, and E. Tang. Query-optimal estimation of unitary channels in diamond distance. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 363--390, Los Alamitos, CA, USA, nov 2023. IEEE Computer Society. https://doi....

2023
[14]

Learning quantum hamiltonians from high-temperature gibbs states and real-time evolutions

Jeongwan Haah, Robin Kothari, and Ewin Tang. Learning quantum hamiltonians from high-temperature gibbs states and real-time evolutions. Nature Physics , 20:1027--1031, june 2024. https://doi.org/10.1038/s41567-023-02376-x doi:10.1038/s41567-023-02376-x

2024 doi
[15]

Learning many-body hamiltonians with heisenberg-limited scaling

Hsin-Yuan Huang, Yu Tong, Di Fang, and Yuan Su. Learning many-body hamiltonians with heisenberg-limited scaling. Phys. Rev. Lett. , 130:200403, May 2023. https://doi.org/10.1103/PhysRevLett.130.200403 doi:10.1103/PhysRevLett.130.200403

2023 doi
[16]

Universal quantum simulators

Seth Lloyd. Universal quantum simulators. Science , 273(5278):1073--1078, 1996. https://doi.org/10.1126/science.273.5278.1073 doi:10.1126/science.273.5278.1073

1996
[17]

Ashley Montanaro and Tobias J. Osborne. Quantum boolean functions, 2010. URL: https://arxiv.org/abs/0810.2435, http://arxiv.org/abs/0810.2435 arXiv:0810.2435

2010 arXiv
[18]

A Survey of Quantum Property Testing

Ashley Montanaro and Ronald de Wolf. A Survey of Quantum Property Testing . Number 7 in Graduate Surveys. Theory of Computing Library, 2016. https://doi.org/10.4086/toc.gs.2016.007 doi:10.4086/toc.gs.2016.007

2016 doi
[19]

Unitary Property Testing Lower Bounds by Polynomials

Adrian She and Henry Yuen. Unitary Property Testing Lower Bounds by Polynomials . In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , volume 251 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 96:1--96:17...

2023 doi
[20]

Quantum Approximate Counting with Nonadaptive Grover Iterations

Ramgopal Venkateswaran and Ryan O'Donnell. Quantum Approximate Counting with Nonadaptive Grover Iterations . In Markus Bl\" a ser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) , volume 187 of Leibniz Interna...

2021 doi
[21]

Quantum Information Theory

Mark M Wilde. Quantum Information Theory . Cambridge university press, 2 edition, 2017

2017

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [1]

Sample-efficient learning of interacting quantum systems

Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahar, and Mehdi Soleimanifar. Sample-efficient learning of interacting quantum systems. Nature Physics , 17:931--935, Aug 2021. https://doi.org/10.1038/s41567-021-01232-0 doi:10.1038/s41567-021-01232-0

doi:10.1038/s41567-021-01232-0 2021

[2] [2]

The Quantum PCP Conjecture

Dorit Aharonov, Itai Arad, and Thomas Vidick. The quantum PCP conjecture, 2013. http://arxiv.org/abs/1309.7495 arXiv:1309.7495

work page Pith review arXiv 2013

[3] [3]

Testing and learning structured quantum hamiltonians, 2024

Srinivasan Arunachalam, Arkopal Dutt, and Francisco Escudero Gutiérrez. Testing and learning structured quantum hamiltonians, 2024. http://arxiv.org/abs/2411.00082 arXiv:2411.00082

arXiv 2024

[4] [4]

Caro, and Aadil Oufkir

Andreas Bluhm, Matthias C. Caro, and Aadil Oufkir. Hamiltonian Property Testing , 2024. http://arxiv.org/abs/2403.02968 arXiv:2403.02968

arXiv 2024

[5] [5]

Quantum Amplitude Amplification and Estimation , 2002

Gilles Brassard, Peter H yer, Michele Mosca, and Alain Tapp. Quantum Amplitude Amplification and Estimation , 2002. https://doi.org/10.1090/conm/305/05215 doi:10.1090/conm/305/05215

doi:10.1090/conm/305/05215 2002

[6] [6]

Learning quantum hamiltonians at any temperature in polynomial time

Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang. Learning quantum hamiltonians at any temperature in polynomial time. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , STOC 2024, page 1470–1477, New York, NY, USA, 2024. Association for Computing Machinery. https://doi.org/10.1145/3618260.3649619 doi:10.1145/3618260.3649619

arXiv 2024

[7] [7]

Structure learning of hamiltonians from real-time evolution

Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang. Structure learning of hamiltonians from real-time evolution. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1037--1050, 2024. https://doi.org/10.1109/FOCS61266.2024.00069 doi:10.1109/FOCS61266.2024.00069

arXiv 2024

[8] [8]

Childs, Dmitri Maslov, Yunseong Nam, Neil J

Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su. Toward the first quantum simulation with quantum speedup. Proceedings of the National Academy of Sciences , 115(38):9456--9461, 2018. https://doi.org/10.1073/pnas.1801723115 doi:10.1073/pnas.1801723115

doi:10.1073/pnas.1801723115 2018