We address the problem of testing whether an unknown $n$-qudit state $ρ$ is $a$-close to a product state or $b$-far away from any product state, as measured in terms of state overlap. We provide a time-efficient algorithm to solve this problem that requires an $n$-independent number of copies of the unknown state. Our random coloring argument shows that for any unknown state there always exists a partition of $[n]$ into $q$ parts such that the square of the overlap with the closest product state with respect to this partition is only an additive factor $O(1/q)$ larger. This reduces the problem to tolerant testing of $q$ parties, with potentially growing local dimensions. Combining this insight with blockwise spectral projection arguments we can show that the natural $k$-copy generalization of Harrow & Montanaro's product state test provides an efficient tolerant tester.
We use the same random coloring and blockwise spectral projection techniques to obtain a substantially improved algorithm for closest product state learning. In particular we give an algorithm that takes in $\widetilde{O}\big((nd)^2\big)\, 2^{\widetilde{O}(1/\varepsilon^8)}$ copies of the unknown state and produces an $\varepsilon$-approximately optimal product state. The key technical components of this learner are a qudit variant of the Bakshi et al. high-fidelity product state learning algorithm and a sampling technique based on Werner's optimal cloning channel.
We address the problem of testing whether an unknown n-qudit state ρ is a-close to a product state or b-far away from any product state, as measured in terms of state overlap. We provide a time-efficient algorithm to solve this problem that requires an n-independent number of copies of the unknown state. Our random coloring argument shows that for any unknown state there always exists a partition of [n] into q parts such that the square of the overlap with the closest product state with respect to this partition is only an additive factor O(1/q) larger. This reduces the problem to tolerant testing of q parties, with potentially growing local dimensions. Combining this insight with blockwise spectral projection arguments we can show that the natural k-copy generalization of Harrow & Montanaro's product state test provides an efficient tolerant tester.
We use the same random coloring and blockwise spectral projection techniques to obtain a substantially improved algorithm for closest product state learning. In particular we give an algorithm that takes in O((nd)2)2O(1/ε8) copies of the unknown state and produces an ε-approximately optimal product state. The key technical components of this learner are a qudit variant of the Bakshi et al. high-fidelity product state learning algorithm and a sampling technique based on Werner's optimal cloning channel.
Product testing, i.e., deciding whether a pure multipartite quantum state is fully unentangled across a specified tensor decomposition, serves as a bridge between quantum property testing, unentangled quantum proof systems, and tensor optimization. Despite being a fundamental property testing task and having many applications, the product test's exact (worst-case) acceptance probability curve has yet to be fully determined. In this work, we determine this curve exactly. Let ω be the maximum squared overlap of the input with a product state, and let PTn(ω) be the largest possible acceptance probability of the product test over all n-partite pure states with product overlap ω, allowing arbitrary finite local dimensions. We prove that, for every $n\ge 2 $ and every $ω\in(0,1] $, PTn(ω)=21(1+mω2+(1−mω)2), where $m=\lfloor1/ω\rfloor $. The formula recovers the previously known tight section of the curve for $ω\ge 1/2 $, resolves all low-overlap regimes $ω<1/2 $, and implies $\mathrm{PT}_n(ω)\to 1/2 $ as ω→0 answering an open problem in [Soleimanifar and Wright, SODA 2022]. As a complexity-theoretic application, our results improve the one-shot soundness parameter in the Harrow-Montanaro reduction from QMA(k) to QMA(2). Our techniques, built upon those of Soleimanifar and Wright, allow us to resolve these open questions while remaining surprisingly elementary.
We study the problem of finding a (pure) product state with optimal fidelity to an unknown n-qubit quantum state ρ, given copies of ρ. This is a basic instance of a fundamental question in quantum learning: is it possible to efficiently learn a simple approximation to an arbitrary state? We give an algorithm which finds a product state with fidelity ε-close to optimal, using N=npoly(1/ε) copies of ρ and poly(N) classical overhead. We further show that estimating the optimal fidelity is NP-hard for error ε=1/poly(n), showing that the error dependence cannot be significantly improved. For our algorithm, we build a carefully-defined cover over candidate product states, qubit by qubit, and then demonstrate that extending the cover can be reduced to approximate constrained polynomial optimization. For our proof of hardness, we give a formal reduction from polynomial optimization to finding the closest product state. Together, these results demonstrate a fundamental connection between these two seemingly unrelated questions. Building on our general approach, we also develop more efficient algorithms in three simpler settings: when the optimal fidelity exceeds 5/6; when we restrict ourselves to a discrete class of product states; and when we are allowed to output a matrix product state.
Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown n-qudit pure state ∣ψ⟩ that has fidelity τ with some stabilizer state, our algorithm outputs a stabilizer state ∣φ⟩ such that ∣⟨φ∣ψ⟩∣2≥τ−ε with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as (d/τ)O(d2log(1/τ))⋅poly(n,1/ε), where the dimension d is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime τ>cos2(π/8), establishing a qudit analogue of the threshold-based approach in prior qubit work.
Matrix product states (MPS) are a class of physically-relevant quantum states which arise in the study of quantum many-body systems. A quantum state comprised of n qudits is said to be an MPS of bond dimension r if the reduced density matrix ψ1, …, k has rank r for each k ∊ {1, …, n}. When r = 1, this corresponds to the set of product states, i.e. states of the form |ψ1〉 ⊗ ⃛ ⊗ |ψn), which possess no entanglement. For larger values of r, this yields a more expressive class of quantum states, which are allowed to possess limited amounts of entanglement. Devising schemes for testing the amount of entanglement in quantum systems has played a crucial role in quantum computing and information theory. In this work, we study the problem of testing whether an unknown state |ψ〉 is an MPS in the property testing model. In this model, one is given m identical copies of |ψ〉, and the goal is to determine whether |ψ〉 is an MPS of bond dimension r or whether |ψ〉 is far from all such states. For the case of product states, we study the product test, a simple two-copy test previously analyzed by Harrow and Montanaro [17], and a key ingredient in their proof that QMA(2) = QMA(k) for k ≥ 2. We give a new and simpler analysis of the product test which achieves an optimal bound for a wide range of parameters, answering open problems in [17] and [23]. For the case of r ≥ 2, we give an efficient algorithm for testing whether |ψ〉 is an MPS of bond dimension r using m = O(nr2) copies, independent of the dimensions of the qudits, and we show that Ω(n1/2) copies are necessary for this task. This lower bound shows that a dependence on the number of qudits n is necessary, in sharp contrast to the case of product states where a constant number of copies suffices.
We consider the problem of approximate cloning of quantum states: given n copies of an unknown state ρ∈Cd×d, prepare an (n+k)-copy state with high fidelity to ρ⊗(n+k). Werner's pure state cloner is the optimal channel for the pure state case, and shows that n=Θ(kd/ε) copies are necessary and sufficient to clone k additional copies of an unknown pure state to fidelity 1−ε. The random purification channel gives a straightforward extension of Werner's cloner to mixed state inputs: given n copies of a mixed state, randomly purify your input, apply Werner's channel in the larger Hilbert space, and then trace out the auxiliary registers. This gives a mixed state cloner using n=O(krd/ε) copies to clone rank-r states. Can one do any better? We show that the answer is no: one must use n=Ω(krd/ε) copies. We prove our lower bound by studying the special case of projector cloning, in which the input state ρ is promised to be of the form P/r, where P is a rank-r orthogonal projector.
As a further application of our techniques, we consider the closely related problem of approximate transposition of quantum states, where one seeks to convert ρ⊗n to a k-copy state with high fidelity to (ρT)⊗k. Here, we again show n=Θ(krd/ε) copies are necessary and sufficient for this task.
We study the problem of property testing quantum states: given a pure state ∣ψ⟩ that either (A) belongs to some class C of pure states, or (B) is ε-far in trace distance from all states in C, determine which is the case with high probability. It is known that there exists classes C for which the sample complexity of property testing necessarily scales with the size of the system. In this work, we identify classes for which testing only requires a size-independent number of samples. We prove a tight sample complexity of Θ(1/ε2) for the property testing of five important classes of Gaussian quantum states: 1) Fermionic Gaussian states, 2) Slater determinants, 3) bosonic Gaussian states, 4) zero-mean bosonic Gaussian states, and 5) bosonic coherent states.
While property testers for some of these classes have been studied previously, those analyses only gave upper bounds scaling polynomially in the number of modes. In each case, our tester is the projection onto the ``top'' irrep of two or three copies. We get to constant sample complexity by lower bounding how quickly the rejection probability increases with distance from the class; the main technical component involves bounding the spectral gap of symmetric extension of the test projector. We then establish optimality by proving matching lower bounds based on binary state discrimination for each class. Our testers and optimality claims also extend to the tolerant setting, wherein ψ may be O(ε)-close to C in case (A), rather than lying exactly inside.