More Like this

1. Tight Correlation Bounds for Circuits Between AC0 and TC0

   https://doi.org/10.4230/LIPIcs.CCC.2023.18  

   Kumar, Vinayak M. (January 2023, Computational Complexity Conference)

   Ta-Shma, Amnon (Ed.)

   We initiate the study of generalized AC⁰ circuits comprised of arbitrary unbounded fan-in gates which only need to be constant over inputs of Hamming weight ≥ k (up to negations of the input bits), which we denote GC⁰(k). The gate set of this class includes biased LTFs like the k-OR (outputs 1 iff ≥ k bits are 1) and k-AND (outputs 0 iff ≥ k bits are 0), and thus can be seen as an interpolation between AC⁰ and TC⁰. We establish a tight multi-switching lemma for GC⁰(k) circuits, which bounds the probability that several depth-2 GC⁰(k) circuits do not simultaneously simplify under a random restriction. We also establish a new depth reduction lemma such that coupled with our multi-switching lemma, we can show many results obtained from the multi-switching lemma for depth-d size-s AC⁰ circuits lifts to depth-d size-s^{.99} GC⁰(.01 log s) circuits with no loss in parameters (other than hidden constants). Our result has the following applications: - Size-2^Ω(n^{1/d}) depth-d GC⁰(Ω(n^{1/d})) circuits do not correlate with parity (extending a result of Håstad (SICOMP, 2014)). - Size-n^Ω(log n) GC⁰(Ω(log² n)) circuits with n^{.249} arbitrary threshold gates or n^{.499} arbitrary symmetric gates exhibit exponentially small correlation against an explicit function (extending a result of Tan and Servedio (RANDOM, 2019)). - There is a seed length O((log m)^{d-1}log(m/ε)log log(m)) pseudorandom generator against size-m depth-d GC⁰(log m) circuits, matching the AC⁰ lower bound of Håstad up to a log log m factor (extending a result of Lyu (CCC, 2022)). - Size-m GC⁰(log m) circuits have exponentially small Fourier tails (extending a result of Tal (CCC, 2017)). 

   more » « less
2. Learning Shallow Quantum Circuits

   https://doi.org/10.1145/3618260.3649722  

   Huang, Hsin-Yuan; Liu, Yunchao; Broughton, Michael; Kim, Isaac; Anshu, Anurag; Landau, Zeph; McClean, Jarrod R (June 2024, ACM)

   Despite fundamental interests in learning quantum circuits, the existence of a computationally efficient algorithm for learning shallow quantum circuits remains an open question. Because shallow quantum circuits can generate distributions that are classically hard to sample from, existing learning algorithms do not apply. In this work, we present a polynomial-time classical algorithm for learning the description of any unknown 𝑛-qubit shallow quantum circuit 𝑈 (with arbitrary unknown architecture) within a small diamond distance using single-qubit measurement data on the output states of 𝑈. We also provide a polynomial-time classical algorithm for learning the description of any unknown 𝑛-qubit state |𝜓⟩ = 𝑈|0^𝑛⟩ prepared by a shallow quantum circuit 𝑈 (on a 2D lattice) within a small trace distance using single-qubit measurements on copies of |𝜓⟩. Our approach uses a quantum circuit representation based on local inversions and a technique to combine these inversions. This circuit representation yields an optimization landscape that can be efficiently navigated and enables efficient learning of quantum circuits that are classically hard to simulate. 

   more » « less
3. Compiling Quantum Circuits for Dynamically Field-Programmable Neutral Atoms Array Processors

   https://doi.org/10.22331/q-2024-03-14-1281  

   Tan, Daniel Bochen; Bluvstein, Dolev; Lukin, Mikhail D; Cong, Jason (March 2024, Quantum)

   Dynamically field-programmable qubit arrays (DPQA) have recently emerged as a promising platform for quantum information processing. In DPQA, atomic qubits are selectively loaded into arrays of optical traps that can be reconfigured during the computation itself. Leveraging qubit transport and parallel, entangling quantum operations, different pairs of qubits, even those initially far away, can be entangled at different stages of the quantum program execution. Such reconfigurability and non-local connectivity present new challenges for compilation, especially in the layout synthesis step which places and routes the qubits and schedules the gates. In this paper, we consider a DPQA architecture that contains multiple arrays and supports 2D array movements, representing cutting-edge experimental platforms. Within this architecture, we discretize the state space and formulate layout synthesis as a satisfiability modulo theories problem, which can be solved by existing solvers optimally in terms of circuit depth. For a set of benchmark circuits generated by random graphs with complex connectivities, our compiler OLSQ-DPQA reduces the number of two-qubit entangling gates on small problem instances by 1.7x compared to optimal compilation results on a fixed planar architecture. To further improve scalability and practicality of the method, we introduce a greedy heuristic inspired by the iterative peeling approach in classical integrated circuit routing. Using a hybrid approach that combined the greedy and optimal methods, we demonstrate that our DPQA-based compiled circuits feature reduced scaling overhead compared to a grid fixed architecture, resulting in 5.1X less two-qubit gates for 90 qubit quantum circuits. These methods enable programmable, complex quantum circuits with neutral atom quantum computers, as well as informing both future compilers and future hardware choices. 

   more » « less
4. Reconstruction algorithms for low-rank tensors and depth-3 multilinear circuits

   https://doi.org/10.1145/3406325.3451096  

   Bhargava, Vishwas; Saraf, Shubhangi; Volkovich, Ilya (June 2021, STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing)

   null (Ed.)

   We give new and efficient black-box reconstruction algorithms for some classes of depth-3 arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a constant-rank tensor. More specifically, we provide efficient learning algorithms that run in randomized polynomial time over general fields and in deterministic polynomial time over and for the following classes: 1) Set-multilinear depth-3 circuits of constant top fan-in ((k) circuits). As a consequence of our algorithm, we obtain the first polynomial time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank tensors. This result holds for d dimensional tensors for any d, but is interesting even for d=3. 2) Sums of powers of constantly many linear forms ((k) circuits). As a consequence we obtain the first polynomial-time algorithm for tensor rank computation and optimal tensor decomposition of constant-rank symmetric tensors. 3) Multilinear depth-3 circuits of constant top fan-in (multilinear (k) circuits). Our algorithm works over all fields of characteristic 0 or large enough characteristic. Prior to our work the only efficient algorithms known were over polynomially-sized finite fields (see. Karnin-Shpilka 09’). Prior to our work, the only polynomial-time or even subexponential-time algorithms known (deterministic or randomized) for subclasses of (k) circuits that also work over large/infinite fields were for the setting when the top fan-in k is at most 2 (see Sinha 16’ and Sinha 20’). 

   more » « less
5. Shallow-Depth Quantum Circuit for an Unstructured Database Search

   https://doi.org/10.3390/quantum6040037  

   Zhan, Junpeng (October 2024, Quantum Reports)

   Grover’s search algorithm (GSA) offers quadratic speedup in searching unstructured databases but suffers from exponential circuit depth complexity. Here, we present two quantum circuits called HX and Ry layers for the searching problem. Remarkably, both circuits maintain a fixed circuit depth of two and one, respectively, irrespective of the number of qubits used. When the target element’s position index is known, we prove that either circuit, combined with a single multi-controlled X gate, effectively amplifies the target element’s probability to over 0.99 for any qubit number greater than seven. To search unknown databases, we use the depth-1 Ry layer as the ansatz in the Variational Quantum Search (VQS), whose efficacy is validated through numerical experiments on databases with up to 26 qubits. The VQS with the Ry layer exhibits an exponential advantage, in circuit depth, over the GSA for databases of up to 26 qubits. 

   more » « less