More Like this

1. Deeper Shallow Embeddings

   Prinz, Jacob; Kavvos, G. A.; Lampropoulos, Leonidas (January 2022, International Conference on Interactive Theorem Proving)
2. Deep and Shallow Types

   https://doi.org/10.17760/D20398329  

   Ben Greenman (January 2022, Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation)

   Sound gradual types come in many forms and offer varying levels of soundness. Two extremes are deep types and shal- low types. Deep types offer compositional guarantees but depend on expensive higher-order contracts. Shallow types enforce only local properties, but can be implemented with first-order checks. This paper presents a language design that supports both deep and shallow types to utilize their complementary strengths. In the mixed language, deep types satisfy a strong com- plete monitoring guarantee and shallow types satisfy a first- order notion of type soundness. The design serves as the blueprint for an implementation in which programmers can easily switch between deep and shallow to leverage their dis- tinct advantages. On the GTP benchmark suite, the median worst-case overhead drops from several orders of magnitude down to 3x relative to untyped. Where an exhaustive search is feasible, 40% of all configurations run fastest with a mix of deep and shallow types. 

   more » « less
3. 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
4. Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

   https://doi.org/10.1145/3313276.3316404  

   Watts, Adam Bene; Kothari, Robin; Schaeffer, Luke; Tal, Avishay (June 2019, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing)

   Recently, Bravyi, Gosset, and Konig (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (or NC^0 circuits). In other words, they exhibited a search problem in QNC^0 that is not in NC^0. We strengthen their result by proving that the 2D HLF problem is not contained in AC^0, the class of classical, polynomial-size, constant-depth circuits over the gate set of unbounded fan-in AND and OR gates, and NOT gates. We also supplement this worst-case lower bound with an average-case result: There exists a simple distribution under which any AC^0 circuit (even of nearly exponential size) has exponentially small correlation with the 2D HLF problem. Our results are shown by constructing a new problem in QNC^0, which we call the Parity Halving Problem, which is easier to work with. We prove our AC^0 lower bounds for this problem, and then show that it reduces to the 2D HLF problem. 

   more » « less
5. Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

   Watts, Adam Bene; Kothari, Robin; Schaeffer, Luke; Tal, Avishay (June 2019, Proceedings of the Annual ACM Symposium on Theory of Computing)