More Like this

1. 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
2. DFSSD: Deep Faults and Shallow State Duality, A Provably Strong Obfuscation Solution for Circuits with Restricted Access to Scan Chain

   https://doi.org/10.1109/VTS48691.2020.9107629  

   Roshanisefat, Shervin ; Kamali, Hadi Mardani ; Zamiri Azar, Kimia ; Pudukotai Dinakarrao, Sai Manoj ; Karimi, Naghmeh ; Homayoun, Houman ; Sasan, Avesta ( April 2020 , 2020 IEEE 38th VLSI Test Symposium (VTS))

   Abstract—In this paper, we introduce DFSSD, a novel logic locking solution for sequential and FSM circuits with a restricted (locked) access to the scan chain. DFSSD combines two techniques for obfuscation: (1) Deep Faults, and (2) Shallow State Duality. Both techniques are specifically designed to resist against sequential SAT attacks based on bounded model checking. The shallow state duality prevents a sequential SAT attack from taking a shortcut for early termination without running an exhaustive unbounded model checker to assess if the attack could be terminated. The deep fault, on the other hand, provides a designer with a technique for building deep, yet key recoverable faults that could not be discovered by sequential SAT (and bounded model checker based) attacks in a reasonable time. 

   more » « less
3. Signatures of interacting Floquet phases in shallow quantum circuits

   https://doi.org/10.1103/PhysRevB.106.214310  

   Su, Kaixiang ; Lawler, Michael J. ( December 2022 , Physical Review B)
4. Efficient Classical Simulation of Random Shallow 2D Quantum Circuits

   https://doi.org/10.1103/PhysRevX.12.021021  

   Napp, John C. ; La Placa, Rolando L. ; Dalzell, Alexander M. ; Brandão, Fernando G. S. L. ; Harrow, Aram W. ( April 2022 , Physical Review X)
5. LAGOS-NE Shallow Lakes: a dataset of lake variables and multi-scaled ecological context variables used to predict and compare trophic status and TP:CHLa relationships between shallow and non-shallow lakes in the Upper Midwest and Northeastern United States.

   https://doi.org/10.6073/pasta/be49507b941815d7a6807a273ee02d1e  

   Cheruvelil, Kendra S. ; Webster, Katherine E. ; King, Katelyn B. ; Poisson, Autumn C. ; Wagner, Tyler ( January 2022 , Environmental Data Initiative)

   We conducted a macroscale study of 2,210 shallow lakes (mean depth ≤ 3m or a maximum depth ≤ 5m) in the Upper Midwestern and Northeastern U.S. We asked: What are the patterns and drivers of shallow lake total phosphorus (TP), chlorophyll a (CHLa), and TP–CHLa relationships at the macroscale, how do these differ from those for 4,360 non-shallow lakes, and do results differ by hydrologic connectivity class? To answer this question, we assembled the LAGOS-NE Shallow Lakes dataset described herein, a dataset derived from existing LAGOS-NE, LAGOS-DEPTH, and LAGOS-CLIMATE datasets. Response data variables were the median of available summer (e.g., 15 June to 15 September) values of total phosphorus (TP) and chlorophyll a (CHLa). Predictor variables were assembled at two spatial scales for incorporation into hierarchical models. At the local or lake-specific scale (including the individual lake, its inter-lake watershed [iws] or corresponding HU12 watershed), variables included those representing land use/cover, hydrology, climate, morphometry, and acid deposition. At the regional scale (e.g., HU4 watershed), variables included a smaller set of predictor variables for hydrology and land use/cover. The dataset also includes the unique identifier assigned by LAGOS-NE(lagoslakeid); the latitude and longitude of the study lakes; their maximum and mean depths along with a depth classification of Shallow or non-Shallow; connectivity class (i.e., whether a lake was classified as connected (with inlets and outlets) or unconnected (lacking inlets); and the zone id for the HU4 to which each lake belongs. Along with the database, we provide the R scripts for the hierarchical models predicting TP or CHLa (TPorCHL_predictive_model.R), and the TP—CHLa relationship (TP_CHL_CSI_Model.R) for depth and connectivity subsets of the study lakes. 

   more » « less