CS Paper Radar

Deterministic Preparation of Arbitrary Spin Eigenfunctions

Wenxuan Tao, Jianan Wang, Fen Zuo

cs.DS quant-phcond-mat.str-elphysics.chem-ph ·submitted 2026-08-24 07:22 UTC · v1

Abstract

Quantum states with conserved total spins, or spin eigenfunctions, are important for studying quantum chemistry and quantum manybody physics problems. A typical class of spin eigenfunctions are Dicke states, which attain maximal spins. While we already have many efficient quantum algorithms to prepare Dicke states, it is not yet clear if we could do so for arbitrary spin eigenfunctions deterministically. Generalizing Bärtschi and Eidenbenz's elegant algorithms for Dicke state preparation, we successfully prepare arbitrary spin eigenfunctions characterized by branching paths and binary spin trees. As a byproduct, we also develop the corresponding classical algorithms to reconstruct all these spin states.

Comment
38 pages, 14 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Fast Algorithms for Stoquastic Spin Systems

cs.CC quant-phcs.DSmath.CO ·2026-08-19 ·Ryan L. Mann
similarity 0.55
Abstract · 30 pages, 0 figures

We establish a general framework for developing fast sampling and counting algorithms for stoquastic spin systems at high temperature. Our framework is based on a rapidly mixing Markov chain for polymer models and a subcritical percolation process for sampling individual polymers. We apply our framework to obtain fast algorithms for approximating the partition function and sampling from the thermal distribution of (1) general stoquastic spin systems, (2) ferromagnetic Heisenberg models, and (3) antiferromagnetic Heisenberg models on bipartite graphs. For the Heisenberg models, we obtain an improved bound on the inverse temperature by using their respective cycle and loop representations.

0.44

Spin Vector Control for Heisenberg-Inspired Probabilistic Computing

cs.ET cond-mat.mes-hall ·2026-08-12 ·Yuanqiu Tan, Rahul Tripathi, Saleh Bunaiyan, Ryan Wagner, Neil Dilley +3 more
published similarity 0.53
Abstract · 37 pages, 11 figures, 1 table

Probabilistic bits (p-bits) have emerged as a cornerstone of probabilistic computing, enabling energy-efficient hardware implementation for probabilistic inference and combinatorial optimization. A critical challenge in advancing this field beyond binary p-bits lies in realizing and manipulating vector spin information, essential for mapping complex energy-based models such as the Heisenberg Hamiltonian.Here, we demonstrate a spintronic platform capable of real-space vector summation by using dual ferromagnetic spin injections into a monolayer graphene channel. By electrically tuning the spin polarization through independently controlled injection currents, we achieve continuous control over the magnitude and direction of the resulting spin accumulation vector. Experimental observations, supported by theoretical vector summation models and spin-circuit simulations, reveal coherent vector interactions and angular tunability of the spin state. This approach enables direct implementation of vector-based spin logic and lays the groundwork for mapping classical Heisenberg models using stochastic low-barrier magnets. Our results establish a scalable pathway for realizing probabilistic spin circuits based on two-dimensional materials, offering new opportunities for low-power, non-Boolean computing architectures.

0.25

Beyond light cones: State preparation complexity in quantum spin glasses

cs.CC quant-phcond-mat.dis-nnmath.PR ·2026-10-01 ·Omar Al-Ghattas, David Gamarnik, Bobak T Kiani
benchmarktheoryhot direction similarity 0.53
Abstract · 102 pages

We introduce a technique for studying state preparation complexity in the quantum $p$-spin model on $n$ qubits, a disordered quantum spin system with random interactions on every set of $p$ qubits. We reduce the task of proving state preparation lower bounds to bounding the local profile complexity of the class, a quantity derived from the metric entropy of the set of vectors recording each state's expectation values against all weight-$p$ Pauli strings. We show that, for sufficiently large fixed $p$, any class with local profile complexity $O(n^2)$ remains separated from the ground-state energy by $Ω(\sqrt n)$, a gap on the leading energy scale. When the profile complexity is $o(n^2)$, we prove the stronger conclusion that the class cannot outperform a benchmark class of simpler states at leading order. Product states always provide such a benchmark. Our framework strengthens known bounds and covers classes beyond the reach of previous methods. These include examples where circuit lightcones extend across the entire system, preventing an application of standard arguments. We obtain an $Ω(n^2/\log n)$ gate lower bound for preparing near-ground states and depth--width tradeoffs, allowing arbitrary one- and two-qubit gates and arbitrarily many discardable ancillas. We also derive lower bounds on entanglement depth and matrix product state bond dimension, and energy obstructions for forward and reverse magic at every fixed level of Parham's magic hierarchy (arXiv:2504.19966). For Clifford circuits doped with $T$-gates, we obtain sharper energy comparisons using product stabilizer states as a more restrictive benchmark. The proof combines an adaptation of a nonsymmetric quantum de Finetti theorem (arXiv:1810.12197) with metric-entropy bounds for the Gaussian process indexed by the local profiles of states in the class.

0.31

Hardness of Pathfinding in a Welded Tree

cs.CC quant-ph ·2026-09-17 ·David Miloschewsky, Supartha Podder
theory similarity 0.52
Abstract · 55 pages, 4 figures

Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open question whether any quantum algorithm is able to efficiently find a path from the entrance to the exit. We answer this by proving an exponential quantum query lower bound for finding such path. Specifically, for trees of height $n$, any quantum query algorithm requires at least $Ω(2^{n/24})$ queries in order to succeed with constant probability. Our proof uses the compressed permutation oracle technique in order to construct databases which track the graph information an algorithm has learned and forgotten, and show that no efficient quantum algorithm can build an entrance-to-exit path in these records.

0.29

Efficient classical simulation of Fermi-Hubbard models with Kramers symmetry

cs.DS cond-mat.stat-mechcond-mat.str-elquant-ph ·2026-11-05 ·Chaithanya Rayudu, Jun Takahashi, Ojas Parekh, Andrew Zhao
theory similarity 0.51
Abstract · 36 pages

Quantum Monte Carlo methods are widely used to solve quantum many-body problems. However, rigorous guarantees for their performance are poorly understood, especially for simulating interacting fermions. In this work, we develop a quantum Monte Carlo algorithm for a broad family of fermionic systems exhibiting Kramers time-reversal symmetry, and prove that their partition functions can be estimated in polynomial time. This family, which contains many important classes of Hubbard-type models, is known to both avoid the sign problem and obey a Lee-Yang zero-freeness theorem. Thus our results suggest that these two properties together may enable efficient classical algorithms for quantum many-body systems more broadly.

0.15

Deterministic Approximation of the Total Variation Distance Between Spin Systems

cs.DS ·2026-10-08 ·Zelin Li, Minji Yang
similarity 0.51
Abstract

We study deterministic relative approximation of the total variation distance between two Gibbs distributions induced by spin systems on the same bounded-degree graph. For the hard-core model, we give a deterministic polynomial-time $\varepsilon$-relative-error approximation when both external-field vectors lie in $[b,(1-η)λ_{\mathrm c}(Δ)]^V$, where $b>0$ and $η\in(0,1)$ are fixed and $λ_{\mathrm c}(Δ)$ is the hard-core uniqueness threshold. For the Ising model, we obtain deterministic polynomial-time algorithms in two settings: the ferromagnetic Lee--Yang regime and the antiferromagnetic correlation-decay regime. We develop a new deterministic framework that reduces this task to estimating suitably chosen partition functions.

0.23

On the Computational Complexity of Guided Berry Phase Estimation

cs.CC quant-ph ·2026-09-22 ·Gabriel Waite
theory similarity 0.50
Abstract · 41 + 30 pages; 8 figures. v1: comments welcome

We prove that deciding the Berry phase for parameterised 2-local qubit Hamiltonians is BQP-complete when presented with a classical description of a guiding state, promised to overlap with the ground state of the system. Our results extend to systems with weighted Heisenberg interactions and when restricted to a 2D square or triangular lattice geometry. The techniques we develop leverage the Schrieffer--Wolff transformation, typically used in the construction of perturbative gadget reductions for local Hamiltonian problems, extending it to parameterised families of Hamiltonians. We demonstrate that there exists a choice of parameterised simulator Hamiltonians whose Berry phase well-approximates that of a parameterised target family. Using the perturbative gadget reduction framework of Oliveira and Terhal and of Schuch and Verstraete, we adapt the arguments to parameterised interactions and demonstrate the error bounds in the resulting simulation can be controlled. Additionally, we provide an explicit proof that families of 1-local Hamiltonians have a Berry phase that can be efficiently computed to inverse-polynomial precision. This establishes a complexity transition between 1-local and 2-local Hamiltonian families.

0.54

Clifford synthesis is NP-complete

cs.CC quant-ph ·2026-10-29 ·Søren Fuglede Jørgensen
similarity 0.50
Abstract

We show that the problem of synthesizing a quantum circuit for a given Clifford operator using at most a specified amount of resources is NP-complete for several resource models of practical interest. Specifically, we study synthesis of a given Clifford operator using single-qubit Clifford gates and two-qubit Clifford gates, with full qubit connectivity and no additional ancilla qubits. With single-qubit gates free and CNOT as the only two-qubit gate, we show that deciding whether a given target admits an implementation using at most a specified number of CNOT gates is NP-complete, and we show that the problem remains NP-complete when any two-qubit Clifford gate is allowed and the budget counts all such gates. Moreover, we show that both results continue to hold when SWAP gates may be inserted for free, and when single-qubit gates are also considered part of the budget. In each case, we build on recent work by Li and Guan and show that there are polynomial-time reductions from Hamiltonian path in grid graphs to these decision problems, using a number of qubits quadratic in the number of grid vertices.

0.05