Sparse Quantum State Preparation with Sublinear T-Count

• URL: http://arxiv.org/abs/2608.00414v1
• Date: Sat, 01 Aug 2026 03:33:19 GMT
• Title: Sparse Quantum State Preparation with Sublinear T-Count
• Abstract summary: We show that any $n$-qubit $s$-sparse state can be prepared up to error $$ using $widetildeO(mins, n3/4sqrts+sqrtslog (1/)+log (1/)$ $T$ gates.<n>For every $0le$ and $2le sle 2n/2$, sparse-state preparation requires $(mins,sqrtns)$ $T
• Score: 5.929956715430168
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the fault-tolerant cost of preparing sparse quantum states, measured by $T$-count in the Clifford+$T$ model. Here an $n$-qubit state is called $s$-sparse if it is supported on at most $s$ computational-basis states. For arbitrary $n$-qubit states, the optimal $T$-count is $Θ(\sqrt{2^n\log(1/ε)}+\log(1/ε))$, but for $s$-sparse states the best previous upper bounds remained linear in $s$. We show that any $n$-qubit $s$-sparse state can be prepared up to error $ε$ using $\widetilde{O}(\min\{s,\ n^{3/4}\sqrt{s}\}+\sqrt{s\log(1/ε)}+\log(1/ε))$ $T$ gates, giving the first sublinear dependence on $s$ once the support is sufficiently large. Our approach is based on a support-aware synthesis theorem for sparse Boolean functions, which may be of independent interest. We also prove that, for every $0<ε\le 1/6$ and $2\le s\le 2^{n/2}$, sparse-state preparation requires $Ω(\min\{s,\sqrt{ns}\})$ $T$ gates, showing that linear dependence on $s$ is unavoidable in the small-support regime and substantially narrowing the gap between the known upper and lower bounds within this parameter range.

Related papers

• 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)
• Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding [26.296743455346604]
  Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM)<n>We study the $T$ count of sparse QROM, in which only $s$ of the $2n$ addresses store nonzero data.<n>Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+$T$ circuits.
  arXiv  Detail & Related papers  (2026-07-30T14:18:29Z)
• 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)
• Is Dimensionality a Barrier for Retrieval Models? [21.1705493494434]
  We show that the best possible margin without a restriction on the dimension, $mathsfmmathsfrd(+infty, A)-2log n)$ can be nearly achieved in dimension $d = O(mathsfmmathsfrd(+infty, A)-2log n)$.<n>Our main theorem establishes that the best possible margin without a restriction on the dimension, $mathsfmmathsfrd(+infty, A)-2log n)$ can be
  arXiv  Detail & Related papers  (2026-05-22T12:22:20Z)
• Quantum state preparation with optimal T-count [1.9402062012850008]
  We show how many T gates are needed to approximate an arbitrary $n$-qubit quantum state to within error $varepsilon$.<n>We also show that this is the optimal T-count for implementing an arbitrary diagonal $n$-qubit unitary to within error $varepsilon$.
  arXiv  Detail & Related papers  (2024-11-07T15:29:33Z)
• Lower bounds on entanglement entropy without twin copy [0.0]
  We calculate the Shannon entropy $S_ABX$ associated with the bitstrings of adiabatically prepared ground states.<n>We show that for a broad range of lattice spacing and detuning, $IX_AB$ is typically 20 percent below $S_AvN$ in regions where $S_AvN$ is large.
  arXiv  Detail & Related papers  (2024-04-15T17:02:17Z)
• Layered State Discovery for Incremental Autonomous Exploration [106.37656068276901]
  Layered Autonomous Exploration (LAE) is a novel algorithm for AX that attains a sample complexity of $tildemathcalO(LSrightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightarrow_LAln12(Srightar row_LAln12(Srightarrow_LAln12
  arXiv  Detail & Related papers  (2023-02-07T22:58:12Z)
• Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom [1.0323063834827415]
  We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. We prove that $omega(log(n))$ $T$-gates are necessary for any Clifford+$T$ circuit to prepare computationally pseudorandom quantum states.
  arXiv  Detail & Related papers  (2022-09-29T03:34:03Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
  We revisit offline reinforcement learning on episodic time-homogeneous Markov Decision Processes with $S$ states, $A$ actions and planning horizon $H$. We obtain the first set of nearly $H$-free sample complexity bounds for evaluation and planning using the empirical MDPs.
  arXiv  Detail & Related papers  (2021-03-25T18:52:17Z)
• 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)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  We prove that an optimistic $Q$-learning enjoys a $mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of states, $A$ is the number of actions, $H$ is the planning horizon, $T$ is the total number of steps, and $Delta_min$ is the minimum sub-optimality gap.
  arXiv  Detail & Related papers  (2020-06-16T13:01:33Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

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.