Optimal T-Count for Block Encodings of Fermionic and Spin Hamiltonians

• URL: http://arxiv.org/abs/2609.11153v1
• Date: Thu, 10 Sep 2026 07:01:08 GMT
• Title: Optimal T-Count for Block Encodings of Fermionic and Spin Hamiltonians
• Abstract summary: We study the cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford$+T$ model.<n>Our main technical tool is an ancilla-compression theorem: any block encoding of an $n$-qubit operator with $a$ clean ancillas and at most $s$ $T$ gates can be compressed to use at most $mina,n+2s$ ancillas.
• Score: 4.914113120082008
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We determine the non-Clifford $T$-gate cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford$+T$ model, when arbitrarily many clean ancillas and unrestricted block-encoding subnormalization are allowed, but without mid-circuit measurements or classical feed-forward. Our main technical tool is an ancilla-compression theorem: any block encoding of an $n$-qubit operator with $a$ clean ancillas and at most $s$ $T$ gates can be compressed to use at most $\min\{a,n+2s\}$ ancillas, without increasing the absolute error or $T$-count. For general second-quantized Hamiltonians with bounded one- and two-body coefficients, at operator-norm block-encoding error $ε$, a volume-covering argument combined with circuit counting gives the worst-case lower bound $Ω(n^2\sqrt{\log(n^4/ε)})$, matching the existing upper bound at fixed precision. For the bond-dependent Kitaev honeycomb family on $n$ spins, we obtain independent lower bounds $Ω(n)$ from stabilizer nullity and $Ω(\log(1/ε))$ from one-qubit state preparation, established using different Hamiltonian instances. Together with an explicit LCU construction, they give the tight worst-case scaling $Θ(n+\log(1/ε))$. As an application, we evaluate the $T$-count of a Hamiltonian simulation circuit based on quantum singular value transformation, with each block-encoding query compiled separately. When phase synthesis and controlled queries add at most constant-factor overhead, the simulation $T$-count scales as the query count times the optimal $T$-count per query.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$ can affect prediction by scale $r_j$ and enters only $n_T,j=T-j+1$ prediction rounds.<n>For every summable envelope, a localized mixture proves $cR_T(r)leq C_T(r)$.<n>For exponential and envelopes, under the stated finite-sample condition, a Toeplitz-design converse proves $cR_T(r)geq c_T(r)$.
  arXiv  Detail & Related papers  (2026-08-27T01:31:46Z)
• Faster quantum linear system solver beyond the condition number [50.84794327094274]
  We present two quantum algorithms that produce the normalized solution $|xrangle$ of linear system $Ax=| b rangle$ to accuracy $$ with complexity independent of the condition number $=lVert A-1rVert$.<n>Our filtering-based solver is extremely simple with a favorable runtime prefactor.
  arXiv  Detail & Related papers  (2026-07-08T17:49:40Z)
• Low-ancilla block encodings via Hamiltonian simulation [10.872863127462717]
  Block encodings are a central primitive in quantum algorithms.<n>We present a simple single-ancilla construction that converts Hamiltonian evolution into a block encoding of the underlying Hamiltonian.
  arXiv  Detail & Related papers  (2026-07-02T08:06:14Z)
• Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing [0.0]
  We find the anti-Hermitian query complexity $d_I = (betaI T + log/varepsilon)/loglog (1/varepsilon)$ to be tight, established via Chebyshev coefficient, modified Bessel functions, and Lambert$W$ inversion.<n>A constant-access-operator construction achieves intrinsic barrier $e-2T$ on a restricted domain, though extension to the full bitorus remains open.
  arXiv  Detail & Related papers  (2026-05-12T19:03:36Z)
• Simulation of Non-Hermitian Hamiltonians with Bivariate Quantum Signal Processing [0.0]
  We achieve query-optimal quantum simulations of non-Hermitian Hamiltonians $H_mathrmeff = H_R + iH_I$, where $H_R$ is Hermitian and $H_I succeq 0$.
  arXiv  Detail & Related papers  (2026-05-12T17:40:56Z)
• On the complexity of quantum numerical integration: an angle-structure characterization [1.376408511310322]
  We study numerical integration on $[0,1]$ by quantum amplitude estimation (QAE), focusing on the cost of constructing the amplitude oracle.<n>We introduce a hierarchy of grid function classes $mathcalG_n(d)$, defined by requiring the angle map $_g:0,1nto[0,]$ to be multi of degree at most $d$.<n>For $d=1$ this becomes $O(varepsilon-1log(1/varepsilon))$, improving over classical Monte Carlo for $ge
  arXiv  Detail & Related papers  (2026-04-27T10:23:24Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Exponentially faster implementations of Select(H) for fermionic Hamiltonians [0.0]
  We present a framework for constructing quantum circuits that implement the multiply-controlled unitary $textSelect(H) equiv sum_ell. $textSelect(H)$ is one of the main subroutines of several quantum algorithms.
  arXiv  Detail & Related papers  (2020-04-08T18:00:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.