Shuchen Zhu

Quantum access to arbitrary classical data encoded in unitary black-box oracles underlies interesting data-intensive quantum algorithms, such as machine learning or electronic structure simulation. The feasibility of these applications depends crucially on gate-efficient implementations of these oracles, which are commonly some reversible versions of the boolean circuit for a classical lookup table. We present a general parameterized architecture for quantum circuits implementing a lookup table that encompasses all prior work in realizing a continuum of optimal tradeoffs between qubits, non-Clifford gates, and error resilience, up to logarithmic factors. Our architecture assumes only local 2D connectivity, yet recovers results, with the appropriate parameters, poly-logarithmic error scaling. We also identify novel regimes, such as simultaneous sublinear scaling in all parameters. These results enable tailoring implementations of the commonly used lookup table primitive to any given quantum device with constrained resources.

An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the k-distinctness function on inputs of size N. While the case of k=2 (also called Element Distinctness) is well-understood, there is a polynomial gap between the known upper and lower bounds for all constants k>2. Specifically, the best known upper bound is O(N^{(3/4)-1/(2^{k+2}-4)}) (Belovs, FOCS 2012), while the best known lower bound for k >= 2 is Omega(N^{2/3} + N^{(3/4)-1/(2k)}) (Aaronson and Shi, J.~ACM 2004; Bun, Kothari, and Thaler, STOC 2018). For any constant k >= 4, we improve the lower bound to Omega(N^{(3/4)-1/(4k)}). This yields, for example, the first proof that 4-distinctness is strictly harder than Element Distinctness. Our lower bound applies more generally to approximate degree. As a secondary result, we give a simple construction of an approximating polynomial of degree O(N^{3/4}) that applies whenever k <= polylog(N).

Qudits offer the potential for low-overhead magic state distillation, although previous results for asymptotically good codes have required qudit dimension $q\gg 100$ or code length $\mathcal{N}\gg 100$. These parameters far exceed experimental demonstrations of qudit platforms, and thus motivate the search for better codes. Using a novel lifting procedure, we construct the first family of good triorthogonal codes on the $\mathbb{F}_{2^{2m}}$ alphabet with $m \geq 3$ that lies above the Tsfasman-Vladut-Zink bound. These codes yield a family of asymptotically good quantum codes with transversal CCZ gates, enabling constant space overhead magic state distillation with qudit dimension as small as $q=64$. Further, we identify a promising code with parameters $[[42,14,6]]_{64}$. Finally, we show that a distilled $\ket{CCZ}_{2^{2m}}$ can be reduced to a $\ket{CCZ}_{2^n}$ state for arbitrary $n$ with a constant-depth Clifford circuit of at most 9 computational basis measurements, 12 single-qudit and 9 two-qudit Clifford gates.

We present two deterministic compilation algorithms for single-qutrit unitaries with $\mathcal{O}(\log \frac{1}{\varepsilon})$ gate depth. Each algorithm selects a nearby approximation to the target unitary and then exactly synthesizes the approximation over the Clifford + $\mathbf{R}$ basis. The first algorithm exhaustively searches over the group; while the second algorithm searches only for Householder reflections. The exhaustive search algorithm yields an average $\mathbf{R}$ count of $\yintm + \slopem \log_{10}(1 / \varepsilon)$, albeit with a time complexity of $\mathcal{O}(\varepsilon^{\pgfmathprintnumber[fixed,precision=2]{\fullcomplexity}})$. The Householder search algorithm results in a larger average $\mathbf{R}$ count of $\yint + \slope \log_{10}(1 / \varepsilon)$ at a reduced time complexity of $\mathcal{O}(\varepsilon^{\pgfmathprintnumber[fixed,precision=2]{\householdercomplexity}})$, greatly extending the reach in $\varepsilon$. These costs correspond asymptotically to 35\% and 69\% more non-Clifford gates compared to synthesizing the same unitary with two qubits. Such initial results are encouraging for using the $\mathbf{R}$ gate as the non-transversal gate for qutrit-based computation.

Simulating noiseless quantum dynamics classically faces a fundamental dilemma: tensor-network methods become inefficient as entanglement saturates, while Pauli-truncation approaches typically rely on noise or randomness. To close the gap, we propose the Low-weight Pauli Dynamics (LPD) algorithm that efficiently approximates local observables for short-time dynamics in the absence of noise. We prove that the truncation error admits an average-case bound without assuming randomness, provided that the state is sufficiently entangled. Counterintuitively, entanglement--usually an obstacle for classical simulation--alleviates classical simulation error. We further show that such entangled states can be generated either by tensor-network classical simulation or near-term quantum devices. Therefore, our results establish a rigorous synergy between existing classical simulation methods and provide a complementary route to quantum simulation that reduces circuit depth for long-time dynamics, thereby extending the accessible regime of quantum dynamics.

Efficient block encoding of many-body Hamiltonians is a central requirement for quantum algorithms in scientific computing, particularly in the early fault-tolerant era. In this work, we introduce new explicit constructions for block encoding second-quantized Hamiltonians that substantially reduce Clifford+T gate complexity and ancilla overhead. By utilizing a data lookup strategy based on the SWAP architecture for the \sparnew oracle $O_C$, and a direct sampling method for the \ampnew oracle $O_A$ with SELECT-SWAP architecture, we achieve a T count that scales as $\mathcal{\tilde{O}}(\sqrt{L})$ with respect to the number of interaction terms $L$ in general second-quantized Hamiltonians. We also achieve an improved constant factor in the Clifford gate count of our oracle. Furthermore, we design a block encoding that directly targets the $\eta$-particle subspace, thereby reducing the subnormalization factor from $\mathcal{O}(L)$ to $\mathcal{O}(\sqrt{L})$, and improving fault-tolerant efficiency when simulating systems with fixed particle numbers. Building on the block encoding framework developed for general many-body Hamiltonians, we extend our approach to electronic Hamiltonians whose coefficient tensors exhibit translation invariance or possess decaying structures. Our results provide a practical path toward early fault-tolerant quantum simulation of many-body systems, substantially lowering resource overheads compared to previous methods.

Efficient simulation of quantum dynamics with time-dependent Hamiltonians is important not only for time-varying systems but also for time-independent Hamiltonians in the interaction picture. Such simulations are more challenging than their time-independent counterparts due to the complexity introduced by time ordering. Existing algorithms that aim to capture commutator-based scaling either exhibit polynomial cost dependence on the Hamiltonian’s time derivatives or are limited to low-order accuracy. In this work, we establish the general commutator-scaling error bounds for the truncated Magnus expansion at arbitrary order, where only Hamiltonian terms appear in the nested commutators, with no time derivatives involved. Building on this analysis, we design a high-order quantum algorithm with explicit circuit constructions. The algorithm achieves cost scaling with the commutator structure in the high-precision regime and depends only logarithmically on the Hamiltonian’s time variation, making it efficient for general time-dependent settings, including the interaction picture.

Learning the Hamiltonian governing a quantum system is a central task in quantum metrology, sensing, and device characterization. Existing Heisenberg-limited Hamiltonian learning protocols either require multi-qubit operations that are prone to noise, or single-qubit operations whose frequency or strength increases with the desired precision. These two requirements limit the applicability of Hamiltonian learning on near-term quantum platforms. We present a protocol that learns a quantum Hamiltonian with the optimal Heisenberg-limited scaling using only single-qubit control in the form of static fields with strengths that are independent of the target precision. Our protocol is robust against the state preparation and measurement (SPAM) error. By overcoming these limitations, our protocol provides new tools for device characterization and quantum sensing. We demonstrate that our method achieves the Heisenberg-limited scaling through rigorous mathematical proof and numerical experiments. We also prove an information-theoretic lower bound showing that a non-vanishing static field strength is necessary for achieving the Heisenberg limit unless one employs an extensive number of discrete control operations.