We show that concrete hardness assumptions about learning or cloning the output state of a random quantum circuit can be used as the foundation for secure quantum cryptography. In particular, under these assumptions we construct secure one-way state generators (OWSGs), digital signature schemes, quantum bit commitments, and private key encryption schemes. We also discuss evidence for these hardness assumptions by analyzing the best-known quantum learning algorithms, as well as proving black-box lower bounds for cloning and learning given state preparation oracles. Our random circuit-based constructions provide concrete instantiations of quantum cryptographic primitives whose security do not depend on the existence of one-way functions. The use of random circuits in our constructions also opens the door to NISQ-friendly quantum cryptography. We discuss noise tolerant versions of our OWSG and digital signature constructions which can potentially be implementable on noisy quantum computers connected by a quantum network. On the other hand, they are still secure against noiseless quantum adversaries, raising the intriguing possibility of a useful implementation of an end-to-end cryptographic protocol on near-term quantum computers. Finally, our explorations suggest that the rich interconnections between learning theory and cryptography in classical theoretical computer science also extend to the quantum setting.

We prove a Carbery-Wright style anti-concentration inequality for the unitary Haar measure, by showing that the probability of a polynomial in the entries of a random unitary falling into an $\varepsilon$ range is at most a polynomial in $\varepsilon$. Using it, we show that the scrambling speed of a random quantum circuit is lower bounded: Namely, every input qubit has an influence that is at least inverse exponential in depth, on any output qubit touched by its lightcone. Our result on scrambling speed works with high probability over the choice of a circuit from an ensemble, as opposed to just working in expectation. As an application, we give the first polynomial-time algorithm for learning log-depth random quantum circuits with Haar random gates up to polynomially small diamond distance, given oracle access to the circuit. Other applications of this new scrambling speed lower bound include: $\bullet$ An optimal $Ω(\log \varepsilon^{-1})$ depth lower bound for $\varepsilon$-approximate unitary designs on any circuit architecture; $\bullet$ A polynomial-time quantum algorithm that computes the depth of a bounded-depth circuit, given oracle access to the circuit. Our learning and depth-testing algorithms apply to architectures defined over any geometric dimension, and can be generalized to a wide class of architectures with good lightcone properties.

Quantum computational pseudorandomness has emerged as a fundamental notion that spans connections to complexity theory, cryptography and fundamental physics. However, all known constructions of efficient quantum-secure pseudorandom objects rely on complexity theoretic assumptions. In this work, we establish the first unconditionally secure efficient pseudorandom constructions against shallow-depth quantum circuit classes. We prove that: - Any quantum state 2-design yields unconditional pseudorandomness against both QNC⁰ circuits with arbitrarily many ancillae and AC⁰∘QNC⁰ circuits with nearly linear ancillae. - Random phased subspace states, where the phases are picked using a 4-wise independent function, are unconditionally pseudoentangled against the above circuit classes. - Any unitary 2-design yields unconditionally secure parallel-query pseudorandom unitaries against geometrically local QNC⁰ adversaries, even with limited AC⁰ postprocessing. Our results stand in stark contrast to the standard guarantee of the 2-design property, which only ensures that they cannot be distinguished from Haar random ensembles using two copies or queries. Our work demonstrates that quantum computational pseudorandomness can be achieved unconditionally for natural classes of restricted adversaries, opening new directions in quantum complexity theory.

Given a local Hamiltonian, how difficult is it to determine the entanglement structure of its ground state? We show that this problem is computationally intractable even if one is only trying to decide if the ground state is volume-law vs near area-law entangled. We prove this by constructing strong forms of pseudoentanglement in a public-key setting, where the circuits used to prepare the states are public knowledge. In particular, we construct two families of quantum circuits which produce volume-law vs near area-law entangled states, but nonetheless the classical descriptions of the circuits are indistinguishable under the Learning with Errors (LWE) assumption. Indistinguishability of the circuits then allows us to translate our construction to Hamiltonians. Our work opens new directions in Hamiltonian complexity, for example whether it is difficult to learn certain phases of matter.

Entanglement is a quantum resource, in some ways analogous to randomness in classical computation. Inspired by recent work of Gheorghiu and Hoban, we define the notion of "pseudoentanglement'', a property exhibited by ensembles of efficiently constructible quantum states which are indistinguishable from quantum states with maximal entanglement. Our construction relies on the notion of quantum pseudorandom states -- first defined by Ji, Liu and Song -- which are efficiently constructible states indistinguishable from (maximally entangled) Haar-random states. Specifically, we give a construction of pseudoentangled states with entanglement entropy arbitrarily close to $\log n$ across every cut, a tight bound providing an exponential separation between computational vs information theoretic quantum pseudorandomness. We discuss applications of this result to Matrix Product State testing, entanglement distillation, and the complexity of the AdS/CFT correspondence. As compared with a previous version of this manuscript (arXiv:2211.00747v1) this version introduces a new pseudorandom state construction, has a simpler proof of correctness, and achieves a technically stronger result of low entanglement across all cuts simultaneously.

This article proposes a runtime model that relates server energy consumption to its overall thermal envelope, using hardware performance counters and experimental measurements. While previous studies have attempted system-wide modeling of server power consumption through subsystem models, our approach is different in that it links system energy input to subsystem energy consumption based on a small set of tightly correlated parameters. The proposed model takes into account processor power, bus activities, and system ambient temperature for real-time prediction on the power consumption of long running jobs. Using the HyperTransport and QuickPath Link structures as case studies and through electrical measurements on example server subsystems, we develop a chaotic time-series approximation for runtime power consumption, arriving at the Chaotic Attractor Predictor (CAP). With polynomial time complexity, CAP exhibits high prediction accuracy, having the prediction errors within 1.6% (or 3.3%) for servers based on the HyperTransport bus (or the QuickPath Links), as verified by a set of common processor benchmarks. Our CAP is a superior predictive mechanism over existing linear auto-regressive methods, which require expensive and complex corrective steps to address the nonlinear and chaotic aspects of the underlying physical system.

Distributed processing has been a viable solution for enabling the next generation of real-time wireless sensor networks (WSN). Efficient task scheduling and allocation (TSA) policies guarantee that efficiency of the distribution. However, TSA policies in WSN face the challenges imposed by the wireless communication medium. This makes the accurate evaluation and verification of TSA policies difficult in live systems. Hence, developing a TSA simulator becomes essential to decrease the time for successful development and testing of relevant algorithms. This work addresses the need for a TSA simulator for WSN and develops ETSSI an Energy-based Task Scheduling Simulator. ETSSI is an event-driven, scalable, simulator which provides a user-friendly graphical interface. Its accuracy is more than 80% compared to in-door live implementations on a test bed of Telosb nodes. Most importantly, the TSA policy designer using ETSSI is only concerned about the application model, not the actual application implementation, which is mandatory in today's WSN simulators.

Wireless sensor networks (WSNs) are starting to mature into the next generation where they can be used for adaptive filtering and signal processing, breaking away from the current generation of microcontroller applications. The tasks involved, however, are computationally intensive and strain the energy resources of any single computational sensor node. Moreover, most sensor nodes do not have the computational resources to complete many of these tasks repeatedly. Hence, exploring distributed processing on WSNs becomes a necessity to enable such computational load to be processed in real-time. In this work, a new distributed QR decomposition algorithm, on WSNs, is developed and implemented. QR decomposition has prominent applications in adaptive filtering which is essential for many WSN applications, such as target tracking and beamforming. The contributions of this work can be summarized as follows: (i) developing a new scalable tile-based distributed QR decomposition algorithm, (ii) distributing the least-squares problem based on the proposed distribution of the QR decomposition, (iii) developing resource-aware task allocation and mapping and (iv) developing a simple decentralized transmission scheduling scheme to guarantee efficient operation. This work demonstrates that distributed processing on WSNs paves the way for larger computations beyond the capabilities of a single node. This is accomplished while decreasing the energy per node and increasing the speed of the computation versus the implementation on a single node. The experiments, on a test bed of Telosb sensor nodes, prove that the proposed distributed algorithm enables higher computational capabilities while reducing the energy per node by up to 91.93% and speeding up the computation by up to 79.29% compared with running the QR decomposition on a single node, thus laying the foundation for energy-feasible real-time in-network processing.

Image registration is considered one of the most fundamental and crucial pre-processing tasks in digital imaging. This paper describes a fast multimodal automatic image registration algorithm that handles the alignment of IR and visible images. A multiresolution approach based on dual tree-complex wavelet transform is employed to speed up the process. At the coarsest level, an accurate registration estimate for higher levels is achieved, using edge detection and cross correlation. Mutual information, on the other hand, is applied at higher levels as a matching criterion applied to the six orientation bands of the complex wavelet. The process is completely automatic, and was tested on several sets of synthetic and real data. Experimental results show that the proposed technique exhibits better accuracy than DWT-based algorithms for uni and multi-modal cases.

This paper presents a bottom-up tracking algorithm for surveillance applications where speed and reliability in the case of multiple matches and occlusions are major concerns. The algorithm is divided into four steps. First, moving objects are detected using an accurate hybrid scheme with selective Gaussian modeling. Simple object features balancing speed, reliability, and complexity are then extracted. Objects are matched based on their spatial proximity and feature similarity. Finally, correspondence voting solves multiple match conflicts, segmentation errors, and occlusion cases. This approach is very simple, which makes it suitable for implementation at smart surveillance visual sensing nodes. Moreover, the simulation results demonstrate its robustness in detecting occlusions and correcting segmentation errors without any prior knowledge about the objects models or constraints on the direction of their motion.

Object detection is receiving a growing attention with the emergence of surveillance systems. This paper presents a hybrid adaptive scheme based on selective Gaussian modeling for detecting objects in complex outdoor scenes with gradual illumination changes and dense, moving background objects like swinging tree branches. The proposed technique combines simple frame difference (FD), simple adaptive background subtraction (BS), and accurate Gaussian modeling to benefit from the high detection accuracy of Mixture of Gaussian solution (MoG) in outdoor scenes while reducing the computations required, thus, making it faster and more suitable for real time surveillance applications. Moreover, by applying selective component matching and updating and hysteresis thresholding, the probability of detecting a background pixel as foreground decreases leading to better detection accuracy than MoG as demonstrated in the quantitative and qualitative comparison.

This paper presents a new hybrid image fusion scheme that combines features of pixel and region based fusion, to be integrated in a surveillance system. In such systems, objects can be extracted from the different set of images due to background availability, and transferred to the new composite image with no additional processing usually imposed by other fusion approaches. The background information is then fused in a multi-resolution pixel-based fashion using gradient-based rules to yield a more reliable feature selection. According to Piella and Petrovic quantitative evaluation metrics, the proposed scheme exhibits a superior performance compared to existing fusion algorithms.

With reducing feature sizes, SRAM stability has become a major concern for future technologies. This critical issue can be solved by using highly stable separate bit-line read SRAM cell, but access time improvement becomes critical, since differential sense amplifier cannot be used for single bit-line read operation. In this paper, a novel pseudo differential single ended current mode sense amplifier is proposed. We demonstrate that this design can deliver a performance similar to that of conventional current mode differential amplifier without using dual bit-line for read operation. The overall read operation delay of the proposed single-ended design is almost 60% less than conventional single-ended design in 90nm CMOS technology. The proposed design consumes 51.6% less energy than conventional design counterpart.

One of the ambitious design goals of future generations of wireless systems, including 4G, IEEE 802.11n/802.16 standards, is to reliably provide very high data rate transmission in real-time. This poses a challenge to find an optimal coding scheme that has good performance and can be efficiently implemented in hardware. The most well-known LDPC decoding algorithm is log sum product (log-SP) in which a set of calculations on a non-linear function called Phi-function is approximated by a minimum function. Until now this function has been implemented through look up tables (LUT). But this direct implementation is costly for hardware. Also LUTs are very sensitive to the number of quantization bits and number of LUT values. Therefore, we have proposed analog Phi-function. The design is easily scalable and reconfigurable for larger block sizes. Simulation results show that our proposed design dissipates only 18 nW.