Abstract

Quantum Computation is one of the most promising futures in furthering computing power and increasing the computational scientific simulation ability. However, the present-day quantum devices suffer from several limitations, a small number of qubits, limited connectivity, noisy evolution, and others. Therefore, the need of the hour is to come up with both hardware-based and algorithmic changes to mitigate these limitations and put forth a step toward a quantum computer that achieves supremacy over its classical counterpart. The primary focus of this dissertation is to present a method of efficiently compiling quantum circuits on present-day hardware to minimize the effects of limited connectivity and effects of noise. Further, we explore a class of hybrid quantum-classical algorithms called variational quantum circuits and attempt to characterize their properties, evolution, and advantages. First, we provide the requisite background in quantum computing, variational quantum methods, deep learning, and reinforcement learning. Next, we present qRoute, a reinforcement learning based solution for compiling quantum circuits onto present-day hardware. We elucidate the method that QRoute uses for depth minimized compilation, which is essentially a Monte-Carlo tree search put together with a graph neural network to decide which parts of the tree to explore. We discuss the details of the algorithm, the key points of innovation that differentiate it from the previous methods, and the state-of-the-art results it achieves on various circuits compilation benchmarks. Finally, we move to the application of quantum computers in solving real-world problems and discuss the circuits called variational quantum circuits. We present a framework qLEET for characterizing the training paths, loss landscapes, entanglement capability, and expressibility of these circuits, and we provide a use-case example in analyzing an algorithm called QAOA for computing the Max-Cut of a graph, which is an NP-complete problem and require time exponential in the number of nodes on a classical computer. All code for qRoute and qLEET has been released to the open-source community and provides easy and modular access to endpoints where our algorithms can be tweaked for further research in this domain.

Abstract

Model checking is now a standard technology for verifying large and complex systems. While there are a range of tools and techniques to verify various properties of a system under consideration, in this work, we restrict our attention to safety checking procedures using explicit state space generation. The necessary hardware resources required in this approach depends on the model complexity and the resulting state transition graph that gets generated. This cannot be estimated apriori. For reasonably realistic models, the available main memory in even high end servers may not be sufficient. Hence, we have to use distributed safety verification approaches on a cluster of nodes. However, the problem of estimating the minimum number of nodes in the cluster for the verification procedure to complete successfully remains unsolved. In the thesis, we propose a dynamically scalable model checker using an actor based architecture. Using the proposed approach, an end user can invoke a model checker hosted on a cloud platform in a push button fashion. Our safety verification procedures automatically expands the cluster by requesting more virtual machines from the cloud provider. Finally, the user gets to pay only for the hardware resources he rented for the duration of the verification procedure. We refer to this as Model Checking as Service. We approach this problem by proposing an asynchronous algorithm for safety checking in actor framework. The actor based approach allows for scaling the resources on a need basis and redistributes the work load transparently through state migration. We tested our approach by developing a distributed version of SpinJA model checker using Akka actor framework. We conducted our experiments on Google Cloud Engine (GCE) platform wherein we scale our resources automatically using the GCE API. On large models such as anderson.8 from BEEM benchmark suite, our approach reduced the model checking cost in dollars by 8.6x while reducing the wall clock time to complete the safety checking procedure 5.5x times

Abstract

In the blockchain ecosystem, threshold signature schemes hold a special value. They allow any qualified subset of participants (t-out-of-n) to combine its shares and generate a signature that can be verified using a single threshold public key. This provides not only added decentralization but additional security benefits as well. While there are several existing threshold signature schemes, most are either n-out-of-n and/or require consistent availability of the exact same set of participants through several rounds. This, in turn, results in a bottleneck due to during the various stages of the protocol. This thesis, aims to construct a threshold signature scheme that removes this dependence. We achieve this by introducing non-interactive and truly threshold signatures. This implies that once the message to be signed is revealed, the individual signers can simply sign and broadcast their signature. These individual signatures can then be combined easily to construct the signature for the group without any further involvement. Additionally, the signature scheme also uses misbehavior detection to impose accountability for invalid signing. This is done by adding an optional component to the individual signatures that can be removed while calculating the group signature but later invoked for detection. Finally we prove that our scheme is safe against known distributed attacks and has Existentially Unforgeabilility under Chosen Message Attack (EUF-CMA) security in the Random Oracle Model for up to t − 1 malicious participants.

Abstract

The current generation of quantum devices fall in the noisy intermediate scale quantum (NISQ) era and are afflicted with qubit decoherence issues, scalability problems, circuit trainability and much more. Keeping these issues in mind, quantum-classical hybrid algorithms have been developed that break the problem into tasks for both classical and quantum processors. The classical processor is leveraged for computational tasks like arithmetic operations and optimizations which are easier for classical computers to handle, while computational tasks where quantum processors give better results like solving systems of linear equations come in the "quantum part" of the algorithm. A special class of quantum-classical hybrid algorithms is the variational quantum algorithms (VQAs) which has been used extensively to solve quantum chemistry problems, particle physics problems, optimization problems and much more as they provide a general framework for solving problems. Classical machine learning has recently facilitated many advances in solving problems related to many-body physical systems. Given the intrinsic quantum nature of these problems, it is natural to speculate that quantum-enhanced machine learning will enable us to unveil even greater details than what we currently have. With this motivation, this thesis examines a quantum machine learning approach based on shallow variational ansatz inspired by tensor networks for supervised learning tasks. We first start with an introductory chapter explaining the focus of our works and our contributions. We also discuss the applications of quantum computing in natural sciences. Then we dive into the necessary background of our works in detail. This includes sections on the basics of quantum computing, the NISQ era, variational quantum algorithms, tensor network ansatz and a literature review of the use of tensor networks in quantum computing. We introduce the circuits used by us and explain the tasks tackled in this work. We first look at a preliminary classical image classification task on the FashionMNIST dataset and study the effect of repeating tensor network layers on the ansatz’s expressibility and performance. Finally, we take on the problem of quantum phase recognition for the Transverse Ising and Heisenberg spin models in one and two dimensions, where we were able to reach ≥ 98% test-set accuracies with both multi-scale entanglement renormalization ansatz (MERA) and tree tensor network (TTN) inspired parametrized quantum circuits. Finally, we analyze our results and end with a discussion on the scope of future works.

Abstract

Research in NLP has seen increasing attention toward narrative understanding over the past decade. Narratives have a broad area of applications in various domains such as economics, political science and literature. Understanding narratives is critical to perform well in discourse-level tasks such as summarization, question answering, and multi-hop reasoning. In this thesis, we explore a framework for understanding narratives. Narratives are broken down into two fundamental parts: events and characters. The task of understanding narratives is then posed as the task of understanding the interplay and relations between these two constituents. We focus on two major relations. How are characters related to other characters, i.e. the character-character relations, and how are events related to other events, i.e. event-event relations. We utilize the concept of character arcs, a popular literary device that shows how the character changes with time to model character-character relations. We build MARCUS, an automated pipeline to generate and visualize these character arcs and character relations given a novel. We take two famous literary works, “Harry Potter” and “The Lord of the Rings” and analyze the character relations generated by MARCUS. We evaluate the quality of these arcs and relations through both quantitative and qualitative methods and show the effectiveness of the arcs created through MARCUS. For event-event relations, we focus on the task of identifying temporal relations between an event pair in the narrative. Narratives, by their very nature, are discourse-level phenomenons. Yet, most of the current work on identifying event temporal relations focuses on local event pairs, i.e. event pairs found close together typically within adjacent sentences. We thus, build DELTA, a discourselevel event temporal relation dataset to facilitate document-level event timeline generation. In DELTA, we introduce the concept of multiple timelines, where we distinguish between the real timeline where the events have actually occurred, and hypothetical timelines with events that may not have actually happened. We also develop a new user-friendly annotation tool that not only streamlines and makes the timeline annotation efforts more efficient but also helps visualise and understand the timeline. We train strong baseline models based on RoBERTa to predict discourse-level event temporal relations. In addition, we qualitatively analyze the timelines generated by our dataset, and evaluate these timelines against the timelines generated by existing datasets.

Abstract

Empathy plays a significant role in pervasive cooperation and prosocial behavior among heterogeneous groups of individuals in the animal kingdom. It modulates one's responses to the emotions and pain of others. It enables one to understand and share the feelings of others and then act accordingly and appropriately. The phenomenon of empathy has been researched in several areas such as philosophy, clinical, social and developmental psychology, social and neural sciences, etc. and still a mystery leading to interesting academic research. A plethora of factors have been found to modulate empathy. The aim of this study was to investigate how socioeconomic standing (in particular profession) of an individual (specifically women rape-victims) affects the empathic responses of the participant, both neuronally and behaviourally. This study focuses specifically on empathy towards pain as experienced by another. A three-part experimental study was conducted to explore the neural correlates of empathy in an individual when biased by the knowledge of the profession of the character (female rapevictim). The first part of this study focused on establishing if a bias existed and is reflected in behavioral responses in society towards different career professions opted by women. For this, we conducted an online survey with 21 professions (opted by women) and collected the respectability score. We observed a difference in the average respectability score for different professions thereby confirming the existence of a difference in attitudes towards different professions pursued by women. Progressing on the findings from the first part, the next stage focused on investigating the difference in empathic responses (behaviorally) of individuals towards the pain of others (female rape-victims). Towards this, a second survey was conducted where the participants were presented with the fictional incident of a rape incident narrated as post-incident trauma from the victim’s point of view. The narratives were designed to differ only in depictions of the profession of the victim. Standard questionnaires used to measure empathic responses were presented to participants in addition to the narrative specific questions. We found differences in empathic responses to perceived pain of victims as a function of the profession of the purported rape-victim.

Abstract

The significance of deep neural networks (DNNs) has been well established through its success in a variety of tasks. However, recent studies have shown that DNNs are vulnerable to adversarial examples — inputs crafted by adding small perturbations to the original input. Such perturbations are almost imperceptible to humans but deceive DNNs thus raising major concerns about their utility in real world applications. Although, existing adversarial attack methods in NLP have achieved high success rate in attacking DNNs, they either require detailed information about the target model, training data or need a large amount of queries to generate attacks. Therefore, such attack methods are not realistic as it does not reflect the types of attacks that can be encountered in the real world and are less effective as attacks relying on model information and excessive queries can be easily defended against. In this thesis, we address the above mentioned drawbacks by proposing two realistic attack settings — hard label black box setting and limited query setting. Next, we propose two novel attack methods that crafts plausible and semantically similar adversarial examples in the above settings. The first attack method uses a population based optimization procedure to craft adversarial examples in the hard label black box setting. The second method is a query efficient method that leverages word attention scores and locality sensitive hashing to find important words for substitution in the limited query setting. We benchmark our results across the same search space used in prior attacks so as to ensure fair and consistent comparison. To improve the quality of generated adversarial examples, we propose an alternative method that uses masked language model to find candidate words for substitution by considering the information of both the original word and its surrounding context. We demonstrate the efficacy of each of our proposed approach by attacking NLP models for text classification and natural language inference task. In addition to that we use adversarial examples to evaluate the robustness and generalization of recent math word problem solvers. Our results showcase that DNNs for the above tasks are not robust as they can be deceived by our proposed attack methods in a highly restricted setting. We conduct human evaluation studies to verify the validity and quality of generated adversarial examples.

Abstract

Walking in a virtual environment is a bounded activity. It is challenging to create and navigate in a large virtual environment given a limited physical space. Various techniques like walking on a treadmill, gesture-based walking and redirected walking address this problem in different ways. These existing solutions have challenges like dependency on additional hardware, inability to adopt different room sizes, compromised rendering quality etc. Such trade-offs make the VR setup immobile and expensive for VR applications which require endless locomotion of the participating subjects. We developed a new redirected walking method to allow the subject to walk continuously within a predefined play area without needing additional hardware support. It is a software-oriented system which dynamically generates an endless path for the participant to walk forward continuously. The system is adaptable to varied play area sizes and is highly mobile because no additional hardware setup is required. Redirected walking consists of methods which actively manipulate the virtual environment to fit it in a smaller physical space. Such techniques allow the user to explore a virtual environment larger than the physical space. Covert redirected walking and overt redirected walking are two sub-classes of the redirected walking techniques. Covert techniques manipulate the environment without being perceivable to the user, and overt redirection techniques do such manipulations while being noticed by the user. Our work is classified as an overt redirected walking technique. The system employs a path generation technique which is inspired by the path generation mechanics of mobile-based endless running games. Generally, the path is composed of successive chunks called “Tiles” in the endless running games. The path initially consists of a fixed number of tiles. When the player begins to move forward, a new tile is added towards the end and a tile is removed from the beginning of the path. This behaviour continues until the user terminates the game. Such an approach creates a perception of an infinitely long path and minimizes memory requirements. We designed an endless path generation system which dynamically generates and updates a path within the bounds of the play area. To evaluate the path generation system, we developed a virtual art gallery. The art gallery is an endless, dynamically generated corridor with paintings/art items hanging on the walls. The path generation system generates and updates the gallery when the user moves forward in the gallery. We conducted three user studies to validate our work and gather feedback to check whether the generated environment induces sickness in the subjects and whether it can adjust to different room sizes without affecting the user’s experience of presence and ease of locomotion. In the last and final user study, we employed a simulator sickness questionnaire (SSQ), a presence questionnaire (PQ) and a custom questionnaire (CQ). No significant differences were found in the scores of all three questionnaires between the two different room sizes. We found an overall low score in the experienced realism sub-scale of the PQ, indicating that the subjects didn’t perceive the generated environment as very real. CQ results suggest that the participants walked normally

Abstract

The world has been experiencing rapid urbanization over the last few decades, putting a strain on existing city infrastructure such as waste management, water supply management, public transport and electricity consumption. We are also seeing increasing pollution levels in cities threatening the environment, natural resources and health conditions. However, we must realize that the real growth lies in urbanization as it provides many opportunities to individuals for better employment, healthcare and better education. Cities have now become one of the major contributors to the world’s gross domestic product; therefore, urbanization should always be seen as an opportunity. However, it is imperative to limit the ill effects of rapid urbanization through integrated action plans to enable the development of growing cities. This gave rise to the concept of a smart city in which all available information associated with a city will be utilized systematically for better city management. Needless to say, data associated to the city plays a vital role in understanding the city’s current state and quickly addressing the issues discussed earlier. The systematic collection, processing and analysis of data allow for the incorporation of data intelligence and helps inform decisions on issues that matter to the lives of city residents. City management officials have been collecting data for years; however, their department-centric nature has created data silo issues and made it difficult to manage and share, thus hindering the data analysis process. Considering these issues in existing data systems, this work proposes a novel Smart City data management system architecture to systematically collect, store, exchange and analyze data collected from various sensing nodes depicting smart city applications. The proposed system architecture is divided in subsystems and is discussed in individual chapters. The first chapter introduces and gives overview to the reader of the complete system architecture. The second chapter discusses the data monitoring system (DMS) and data lake system (DLS) based on the oneM2M standards. DMS employs oneM2M as a middleware layer to achieve interoperability, and DLS uses a multi-tenant architecture with multiple logical databases, enabling efficient and reliable data management. The third chapter discusses energy monitoring and electric vehicle charging systems developed to illustrate the applicability of the oneM2M standards. The fourth chapter discusses the Data Exchange System (DES) based on the Indian Urban Data Exchange (IUDX) framework. DES uses IUDX’s standard data schema and open APIs to avoid data silos and enable secure data sharing. The fifth chapter discusses the 5D-IoT framework that provides uniform data quality assessment of sensor data with meaningful data descriptions.

Abstract

Making things, coming up with strange new ideas is what creativity is. The question of where these new ideas come from is the very question that drives all study of creativity. Creativity has to come from the knowledge that exists in the minds of the creator [1]. This work participates in the questions of how we come up with new ideas and to what extent the conceptual space influences creativity. We form concepts through the process of abstraction. Despite having been long established that creativity does not come from the Gods but from our mental and bodily processes, there is very little work on the processes of concept acquisition. There is almost no work that directly studies creativity and abstraction together. This work argues that creativity research assumes an Amodal Symbol cognition structure where the processes of cognition and higher cognitive functions are not related. As a result this relationship has not been explored. This work employs a mixed method approach, using both qualitative and quantitative methods for coding and analysis of abstractions and creative generations. A wordlist based on familiarity, level of abstractness and modality experience was created. A norming study of the rating of abstractness of these words showed significant variability in ratings indicating subjectivity in the perception of abstractness. To study abstractness and creativity a Property Generation and an Alternate Uses task was conducted. Traditional theories of creativity assume we manipulate taxonomic or entity properties in a computer like way, during the process of creativity, however our results emphasises the role of individual experiences in the process of creativity