Saeed Mehraban

STOC Conference 2025 Conference Paper

Improved Bounds for Testing Low Stabilizer Complexity States

• Saeed Mehraban
• Mehrdad Tahmasbi

STOC Conference 2024 Conference Paper

Quadratic Lower Bounds on the Approximate Stabilizer Rank: A Probabilistic Approach

• Saeed Mehraban
• Mehrdad Tahmasbi

The approximate stabilizer rank of a quantum state is the minimum number of terms in any approximate decomposition of that state into stabilizer states. Bravyi and Gosset showed that the approximate stabilizer rank of a so-called “magic” state like | T ⟩ ⊗ n , up to polynomial factors, is an upper bound on the number of classical operations required to simulate an arbitrary quantum circuit with Clifford gates and n number of T gates. As a result, an exponential lower bound on this quantity seems inevitable. Despite this intuition, several attempts using various techniques could not lead to a better than a linear lower bound on the “exact” rank of | T ⟩ ⊗ n , meaning the minimal size of a decomposition that exactly produces the state. For the “approximate” rank, which is more realistically related to the cost of simulating quantum circuits, no lower bound better than Ω(√ n ) has been known. In this paper, we improve the lower bound on the approximate rank to Ω( n 2 ) for a wide range of the approximation parameters. An immediate corollary of our result is the existence of polynomial time computable functions which require a super-linear number of terms in any decomposition into exponentials of quadratic forms over F 2 , resolving a question by Williams. Our approach is based on a strong lower bound on the approximate rank of a quantum state sampled from the Haar measure, a step-by-step analysis of the approximate rank of a magic-state teleportation protocol to sample from the Haar measure, and a result about trading Clifford operations with T gates.

STOC Conference 2020 Conference Paper

Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems

• Aram W. Harrow
• Saeed Mehraban
• Mehdi Soleimanifar

We present a quasi-polynomial time classical algorithm that estimates the partition function of quantum many-body systems at temperatures above the thermal phase transition point. It is known that in the worst case, the same problem is NP-hard below this point. Together with our work, this shows that the transition in the phase of a quantum system is also accompanied by a transition in the hardness of approximation. We also show that in a system of n particles above the phase transition point, the correlation between two observables whose distance is at least Ω(log n ) decays exponentially. We can improve the factor of log n to a constant when the Hamiltonian has commuting terms or is on a 1D chain. The key to our results is a characterization of the phase transition and the critical behavior of the system in terms of the complex zeros of the partition function. Our work extends a seminal work of Dobrushin and Shlosman on the equivalence between the decay of correlations and the analyticity of the free energy in classical spin models. On the algorithmic side, our result extends the scope of a recent approach due to Barvinok for solving classical counting problems to quantum many-body systems.

FOCS Conference 2018 Conference Paper

Approximating the Permanent of a Random Matrix with Vanishing Mean

• Lior Eldar
• Saeed Mehraban

The permanent is #P-hard to compute exactly on average for natural random matrices including matrices over finite fields or Gaussian ensembles. Should we expect that it remains #P-hard to compute on average if we only care about approximation instead of exact computation? In this work we take a first step towards resolving this question: We present a quasi-polynomial time deterministic algorithm for approximating the permanent of a typical n × n random matrix with unit variance and vanishing mean μ = O(ln ln n) -1/8 to within inverse polynomial multiplicative error. (alternatively, one can achieve permanent approximation for matrices with mean μ = 1/polylog(n) in time 2 n(ε), for arbitrarily small ε>0). The proposed algorithm significantly extends the regime of matrices for which efficient approximation of the permanent is known. This is because unlike previous algorithms which require a stringent correlation between the signs of the entries of the matrix [1], [2] it can tolerate random ensembles in which this correlation is negligible (albeit non-zero). Among important special cases we note: 1) Biased Gaussian: each entry is a complex Gaussian with unit variance 1 and mean μ. 2) Biased Bernoulli: each entry is -1 + μ with probability 1/2, and 1 with probability 1/2. These results counter the common intuition that the difficulty of computing the permanent, even approximately, stems merely from our inability to treat matrices with many opposing signs. The Gaussian ensemble approaches the threshold of a conjectured hardness [3] of computing the permanent of a zero mean Gaussian matrix. This conjecture is one of the baseline assumptions of the BosonSampling paradigm that has received vast attention in recent years in the context of quantum supremacy experiments. We furthermore show that the permanent of the biased Gaussian ensemble is #P-hard to compute exactly on average. To our knowledge, this is the first natural example of a counting problem that becomes easy only when average case analysis and approximation are combined. On a technical level, our approach stems from a recent approach taken by Barvinok [1], [4], [5], [6] who used Taylor series approximation of the logarithm of a certain univariate polynomial related to the permanent. Our main contribution is to introduce an average-case analysis of such related polynomials. We complement our approach with a new technique for iteratively computing a Taylor series approximation of a function that is analytical in the vicinity of a curve in the complex plane. This method can be viewed as a computational version of analytic continuation in complex analysis.

STOC Conference 2017 Conference Paper

The computational complexity of ball permutations

• Scott Aaronson
• Adam Bouland
• Greg Kuperberg
• Saeed Mehraban

We define several models of computation based on permuting distinguishable particles (which we call balls) and characterize their computational complexity. In the quantum setting, we use the representation theory of the symmetric group to find variants of this model which are intermediate between BPP and DQC1 (the class of problems solvable with one clean qubit) and between DQC1 and BQP. Furthermore, we consider a restricted version of this model based on an exactly solvable scattering problem of particles moving on a line. Despite the simplicity of this model from the perspective of mathematical physics, we show that if we allow intermediate destructive measurements and specific input states, then the model cannot be efficiently simulated classically up to multiplicative error unless the polynomial hierarchy collapses. Finally, we define a classical version of this model in which one can probabilistically permute balls. We find this yields a complexity class which is intermediate between L and BPP, and that a nondeterministic version of this model is NP-complete.