Abstract

One of the main reasons for query model’s prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show (using the recently introduced spectral sensitivity) that both these bounds (positive adversary and approximate degree) give the same value for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.

Abstract

Standard Model Predictive Control (MPC) or trajectory optimization approaches perform only a local search to solve a complex non-convex optimization problem. As a result, they cannot capture the multi-modal characteristic of human driving. A global optimizer can be a potential solution but is computationally intractable in a real-time setting. In this paper, we present a real-time MPC capable of searching over different driving modalities. Our basic idea is simple: we run several goal-directed parallel trajectory optimizations and score the resulting trajectories based on user-defined meta cost functions. This allows us to perform a global search over several locally optimal motion plans. Although conceptually straightforward, realizing this idea in real-time with existing optimizers is highly challenging from technical and computational standpoints. With this motivation, we present a novel batch nonholonomic trajectory optimization whose underlying matrix algebra is easily parallelizable across problem instances and reduces to computing large batch matrix-vector products. This structure, in turn, is achieved by deriving a linearization-free multi-convex reformulation of the non-holonomic kinematics and collision avoidance constraints. We extensively validate our approach using both synthetic and real data sets (NGSIM) of traffic scenarios. We highlight how our algorithm automatically takes lane-change and overtaking decisions based on the defined meta cost function. Our batch optimizer achieves trajectories with lower meta cost, up to 6x faster than competing baselines.

Abstract

The significance of negative quantum conditional entropy is underscored by its ubiquity in information processing tasks like dense coding, state merging and one-way entanglement distillation. Mere presence of entanglement is not sufficient for these tasks, a fact underpinned by the existence of entangled quantum states with non-negative conditional entropy. This stimulates one to go beyond the paradigm of entanglement theory and probe the hitherto unexplored area of operations influencing quantum conditional entropy. To this end, we introduce the class of A-unital channels. We characterize them and demonstrate that A-unital channels are to states having non-negative conditional entropy what separable channels are to separable states. We also show that A-unital channels form the largest class of channels that do not decrease the conditional entropy of any state, a relation analogous to unital channels and entropy. A comparative study between A-unital and other channels crucial to the resource theory of entanglement is done to further exemplify the distinction with entanglement theory. Non-local unitary operations can decrease conditional entropy to sub-zero levels. However, there exist states whose conditional entropy remains non-negative even under this action. Termed as states having absolute conditional entropy, they prove to be robust against non-local unitary action. In this work, the completely free operations for such states are also characterized. Finally, since von Neumann entropy is the mainspring of these discussions, the bounds on the conditional entropy of states having a given entropy are derived. The definition of A-unital channels naturally lends itself to a procedure for determining membership of channels in this class. Thus, we not only characterize completely free channels for quantum conditional entropy, but also show how resourceful channels can be detected.

Abstract

Quantum chemistry calculations such as the prediction of molecular properties and modeling of chemical reactions are a few of the critical areas where near-term quantum computers can showcase quantum advantage. We present a method to calculate energy derivatives for both ground state and excited state energies with respect to the parameters of a chemical system based on the framework of the variational quantum eigensolver (VQE). A low-depth implementation of quantum circuits within the hybrid variational paradigm is designed, and their computational costs are analyzed. We showcase the effectiveness of our method by incorporating it in some key quantum chemistry applications of energy derivatives, such as to perform minimum energy configuration search and estimate molecular response properties estimation of H2 molecule, and also to find the transition state of H2 + H ↔ H + H2 reaction. The obtained results are shown to be in complete agreement with their respective full configuration interaction (FCI) values. Keywords: Quantum Computing, Quantum Chemistry, Variational Quantum Eigensolver, Hybrid QuantumClassical Algorithms

Abstract

The field of quantum technologies has made rapid strides in recent years, and is poised for significant breakthroughs in the coming years. Practical applications are expected to appear first in sensing and metrology, then in communications and simulations, then as feedback to foundations of quantum theory, and ultimately in computation. The essential features that contribute to these technologies are superposition, entanglement, squeezing and tunneling of quantum states. The theoretical foundation of the field is clear; laws of quantum mechanics are precisely known, and elementary hardware components work as predicted [1, 2]. The challenge is a large scale integration, say of 10 or more components. Quantum systems are highly sensitive to disturbances from the environment; even necessary controls and observations perturb them. The available, and upcoming, quantum devices are noisy, and techniques to bring down the environmental error rate are being intensively pursued. At the same time, it is necessary to come up with error-resilient system designs, as well as techniques that validate and verify the results. This era of noisy intermediate scale quantum systems has been labeled NISQ [

Abstract

The ontological study of Sports and our approach of using graphical representations to analyse, classify and attempt to define sports was preceded by our discovery of a rather little known fact. It is that art competitions were a part of the modern day Olympics for more than three decades, spanning from 1912 to 1948. The inclusion and the eventual exclusion of art competitions in what is today considered the citadel of sporting events caught our attention. The reason for discontinuing art competitions can be traced to the institution's emphasis on ‘amateurship’ on the part of the participants. Artists were considered established professionals whereas sports persons were considered ‘amateur gentlemen’. Although the reason to exclude did not stem from the debate if sport is an artform, the question seemed worthy of our perusal.

Abstract

Accurate identification of the dominant driving factors in the expansion of a city is essential for cellular automata (CA)-based urban expansion modelling. The current study aimed at analyzing the drivers of change for Vijayawada city, a tier-II developing city in south-east Asia, India and then applies them to model the future scenario of the city in a CA-based environment. Furthermore, the study also aims at comparing the efficiency of the renowned CA-based urban growth model, SLEUTH (Slope, Land use, Exclusion, Urban extent, Transportation, Hill shade), and a self-designed CA-based hybrid model developed in combination with genetic algorithm (GA) for developing future scenario of the city. The models were built, calibrated, and validated for the city using land use maps derived from temporal Landsat satellite images. Analysis of the statistical significance of the driving factors shows that the terrain and …

Abstract

The plants of nano air vehicles (NAVs) are generally unstable, adversely coupled, and uncertain. Besides, the autopilot hardware of a NAV has limited sensing and computational capabilities. Hence, these vehicles need a single controller referred to as robust simultaneously stabilizing decoupling (RSSD) output feedback controller that achieves simultaneous stabilization (SS), desired decoupling, robustness, and performance for a finite set of unstable multi-input-multioutput adversely coupled uncertain plants. To synthesize an RSSD output feedback controller, a new method that is based on a central plant is proposed in this article. Given a finite set of plants for SS, we considered a plant in this set that has the smallest maximum v-gap metric as the central plant. Following this, the sufficient condition for the existence of a simultaneous stabilizing controller associated with such a plant is described. The decoupling feature is then appended to this controller using the properties of the eigenstructure assignment method. Afterward, the sufficient conditions for the existence of an RSSD output feedback controller are obtained. Using these sufficient conditions, a new optimization problem for the synthesis of an RSSD output feedback controller is formulated. To solve this optimization problem, a new genetic algorithm-based offline iterative algorithm is developed. The effectiveness of this iterative algorithm is then demonstrated by generating an RSSD controller for a fixed-wing NAV. The performance of this controller is validated through numerical and hardware-in-the-loop simulations.

Abstract

Joint space trajectory optimization under end-effector task constraints leads to a challenging non-convex problem. Thus, a real-time adaptation of prior computed trajectories to perturbation in task constraints often becomes intractable. Existing works use the so-called warm-starting of trajectory optimization to improve computational performance. We present a fundamentally different approach that relies on deriving analytical gradients of the optimal solution with respect to the task constraint parameters. This gradient map characterizes the direction in which the prior computed joint trajectories need to be deformed to comply with the new task constraints. Subsequently, we develop an iterative line-search algorithm for computing the scale of deformation. Our algorithm provides near real-time adaptation of joint trajectories for a diverse class of task perturbations such as (i) changes in initial and final joint configurations of end-effector orientation-constrained trajectories and (ii) changes in end-effector goal or way-points under end-effector orientation constraints. We relate each of these examples to real-world applications ranging from learning from demonstration to obstacle avoidance. We also show that our algorithm produces trajectories with quality similar to what one would obtain by solving the trajectory optimization from scratch with warm-start initialization. But most importantly, our algorithm achieves a worst-case speed-up of 160x over the latter approach.

Abstract

The prose storyboard language is a formal language for de- scribing movies shot by shot, where each shot is described with a unique sentence. The language uses a simple syntax and limited vocabulary borrowed from working practices in traditional movie-making, and is intended to be readable both by machines and humans. The language is designed to serve as a high-level user interface for intelligent cinematog- raphy and editing systems