More Like this

1. Spacetime-Efficient Low-Depth Quantum State Preparation with Applications

   https://doi.org/10.22331/q-2024-02-15-1257  

   Gui, Kaiwen; Dalzell, Alexander M.; Achille, Alessandro; Suchara, Martin; Chong, Frederic T. (February 2024, Quantum)

   We propose a novel deterministic method for preparing arbitrary quantum states. When our protocol is compiled into CNOT and arbitrary single-qubit gates, it prepares an $N$-dimensional state in depth $O(\log (N\left)\right)$and $\text{spacetime allocation}$(a metric that accounts for the fact that oftentimes some ancilla qubits need not be active for the entire circuit) $O\left(N\right)$, which are both optimal. When compiled into the $\left\{\mathrm{H},\mathrm{S},\mathrm{T},\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}\right\}$gate set, we show that it requires asymptotically fewer quantum resources than previous methods. Specifically, it prepares an arbitrary state up to error $ϵ$with optimal depth of $O(\log (N)+\log (1/ϵ\left)\right)$and spacetime allocation $O(N\log (\log \left(N\right)/ϵ\left)\right)$, improving over $O(\log (N)\log (\log \left(N\right)/ϵ\left)\right)$and $O(N\log (N/ϵ\left)\right)$, respectively. We illustrate how the reduced spacetime allocation of our protocol enables rapid preparation of many disjoint states with only constant-factor ancilla overhead – $O\left(N\right)$ancilla qubits are reused efficiently to prepare a product state of $w$ $N$-dimensional states in depth $O(w+\log (N\left)\right)$rather than $O(w\log (N\left)\right)$, achieving effectively constant depth per state. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations. We provide quantum circuit descriptions of our protocol, detailed pseudocode, and gate-level implementation examples using Braket. 

   more » « less
2. On the Computational Hardness of Quantum One-Wayness

   https://doi.org/10.22331/q-2025-03-27-1679  

   Cavalar, Bruno; Goldin, Eli; Gray, Matthew; Hall, Peter; Liu, Yanyi; Pelecanos, Angelos (March 2025, Quantum)

   There is a large body of work studying what forms of computational hardness are needed to realize classical cryptography. In particular, one-way functions and pseudorandom generators can be built from each other, and thus require equivalent computational assumptions to be realized. Furthermore, the existence of either of these primitives implies that $\mathrm{P}\ne \mathrm{N}\mathrm{P}$, which gives a lower bound on the necessary hardness.One can also define versions of each of these primitives with quantum output: respectively one-way state generators and pseudorandom state generators. Unlike in the classical setting, it is not known whether either primitive can be built from the other. Although it has been shown that pseudorandom state generators for certain parameter regimes can be used to build one-way state generators, the implication has not been previously known in full generality. Furthermore, to the best of our knowledge, the existence of one-way state generators has no known implications in complexity theory.We show that pseudorandom states compressing $n$bits to $\log n+1$qubits can be used to build one-way state generators and pseudorandom states compressing $n$bits to $\omega (\log n)$qubits are one-way state generators. This is a nearly optimal result since pseudorandom states with fewer than $c\log n$-qubit output can be shown to exist unconditionally. We also show that any one-way state generator can be broken by a quantum algorithm with classical access to a $\mathrm{P}\mathrm{P}$oracle.An interesting implication of our results is that a $t\left(n\right)$-copy one-way state generator exists unconditionally, for every $t\left(n\right)=o(n/\log n)$. This contrasts nicely with the previously known fact that $O\left(n\right)$-copy one-way state generators require computational hardness. We also outline a new route towards a black-box separation between one-way state generators and quantum bit commitments. 

   more » « less
3. Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond

   Chi-Ning Chou, Peter J. (January 2022, ArXivorg)

   We introduce a notion of \emph{generic local algorithm} which strictly generalizes existing frameworks of local algorithms such as \emph{factors of i.i.d.} by capturing local \emph{quantum} algorithms such as the Quantum Approximate Optimization Algorithm (QAOA). Motivated by a question of Farhi et al. [arXiv:1910.08187, 2019] we then show limitations of generic local algorithms including QAOA on random instances of constraint satisfaction problems (CSPs). Specifically, we show that any generic local algorithm whose assignment to a vertex depends only on a local neighborhood with o(n) other vertices (such as the QAOA at depth less than ϵlog(n)) cannot arbitrarily-well approximate boolean CSPs if the problem satisfies a geometric property from statistical physics called the coupled overlap-gap property (OGP) [Chen et al., Annals of Probability, 47(3), 2019]. We show that the random MAX-k-XOR problem has this property when k≥4 is even by extending the corresponding result for diluted k-spin glasses. Our concentration lemmas confirm a conjecture of Brandao et al. [arXiv:1812.04170, 2018] asserting that the landscape independence of QAOA extends to logarithmic depth -- in other words, for every fixed choice of QAOA angle parameters, the algorithm at logarithmic depth performs almost equally well on almost all instances. One of these concentration lemmas is a strengthening of McDiarmid's inequality, applicable when the random variables have a highly biased distribution, and may be of independent interest. 

   more » « less
4. Explicit Abelian Lifts and Quantum LDPC Codes

   https://doi.org/10.4230/LIPIcs.ITCS.2022.88  

   Jeronimo, Fernando Granha (January 2022, Leibniz international proceedings in informatics)

   Braverman, Mark (Ed.)

   For an abelian group H acting on the set [𝓁], an (H,𝓁)-lift of a graph G₀ is a graph obtained by replacing each vertex by 𝓁 copies, and each edge by a matching corresponding to the action of an element of H. Expanding graphs obtained via abelian lifts, form a key ingredient in the recent breakthrough constructions of quantum LDPC codes, (implicitly) in the fiber bundle codes by Hastings, Haah and O'Donnell [STOC 2021] achieving distance Ω̃(N^{3/5}), and in those by Panteleev and Kalachev [IEEE Trans. Inf. Theory 2021] of distance Ω(N/log(N)). However, both these constructions are non-explicit. In particular, the latter relies on a randomized construction of expander graphs via abelian lifts by Agarwal et al. [SIAM J. Discrete Math 2019]. In this work, we show the following explicit constructions of expanders obtained via abelian lifts. For every (transitive) abelian group H ⩽ Sym(𝓁), constant degree d ≥ 3 and ε > 0, we construct explicit d-regular expander graphs G obtained from an (H,𝓁)-lift of a (suitable) base n-vertex expander G₀ with the following parameters: ii) λ(G) ≤ 2√{d-1} + ε, for any lift size 𝓁 ≤ 2^{n^{δ}} where δ = δ(d,ε), iii) λ(G) ≤ ε ⋅ d, for any lift size 𝓁 ≤ 2^{n^{δ₀}} for a fixed δ₀ > 0, when d ≥ d₀(ε), or iv) λ(G) ≤ Õ(√d), for lift size "exactly" 𝓁 = 2^{Θ(n)}. As corollaries, we obtain explicit quantum lifted product codes of Panteleev and Kalachev of almost linear distance (and also in a wide range of parameters) and explicit classical quasi-cyclic LDPC codes with wide range of circulant sizes. Items (i) and (ii) above are obtained by extending the techniques of Mohanty, O'Donnell and Paredes [STOC 2020] for 2-lifts to much larger abelian lift sizes (as a byproduct simplifying their construction). This is done by providing a new encoding of special walks arising in the trace power method, carefully "compressing" depth-first search traversals. Result (iii) is via a simpler proof of Agarwal et al. [SIAM J. Discrete Math 2019] at the expense of polylog factors in the expansion. 

   more » « less
5. Lower Bounds on Stabilizer Rank

   https://doi.org/10.22331/q-2022-02-15-652  

   Peleg, Shir; Shpilka, Amir; Volk, Ben Lee (February 2022, Quantum)

   The stabilizer rank of a quantum state ψ is the minimal r such that | ψ ⟩ = ∑ j = 1 r c j | φ j ⟩ for c j ∈ C and stabilizer states φ j . The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the n -th tensor power of single-qubit magic states.We prove a lower bound of Ω ( n ) on the stabilizer rank of such states, improving a previous lower bound of Ω ( n ) of Bravyi, Smith and Smolin \cite{BSS16}. Further, we prove that for a sufficiently small constant δ , the stabilizer rank of any state which is δ -close to those states is Ω ( n / log ⁡ n ) . This is the first non-trivial lower bound for approximate stabilizer rank.Our techniques rely on the representation of stabilizer states as quadratic functions over affine subspaces of F 2 n , and we use tools from analysis of boolean functions and complexity theory. The proof of the first result involves a careful analysis of directional derivatives of quadratic polynomials, whereas the proof of the second result uses Razborov-Smolensky low degree polynomial approximations and correlation bounds against the majority function. 

   more » « less