The quantum computing community has been searching for suitable applications to demonstrate the potential of near-term quantum devices. Quantum machine learning is a potential candidate, particularly using models that cannot be efficiently simulated with classical computers [1] , [2] . This work focuses on a transition phase of quantum computers where the quantum machine learning model is still simulable classically but projected not to be simulable as the size of the model grows. Ultimately quantum computers may have advantages for high-dimensional real-world problems. Due to the limited number of qubits in current noisy intermediate-scale quantum (NISQ) devices, the direct application of quantum computers in high dimensional data is not feasible. To remedy this problem, an encoder-decoder architecture can be utilized. The encoder model would transform the high-dimensional data into a compact representation, to a level that small quantum computers can be used today (or in the near future), and the decoder would take the quantum processed outputs back to the high-dimensional space [3] .

Wildfire occurrences have been increasing for the past decade, leaving devastating traces across the world. In the recent ef-forts, remote sensing and airborne missions have been utilized to better understand and manage wildfires. This has resulted in an exponential increase in volume of remote sensing data, which has pushed the need for intelligent automation of data extraction for wildfire studies. Machine learning offers accu-rate automation in detecting such natural anomalies and en-able decision-makers to take actions in a timely manner. Re-cent advances in machine learning algorithms, namely prob-abilistic generative methods, allow researchers and decision- makers to step beyond detection and study “what-if’ scenar-ios for wildfire occurrences. Additionally, they offer better imitations to the stochastic behavior of nature, and wildfire events. However, optimizing the performance of these proba-bilistic generative models is a computationally expensive pro-cess, specially using digital computers. On the other hand, quantum computers have recently shown a promise to reduce computationally costly training of such models and provide performance improvements. There is a body of research in-vestigating the potential for improved machine learning meth-ods in which key operations are performed on a quantum computer. In this study, we propose a probabilistic image-to- image segmentation approach combining a very well-known segmentation method, U-NET, with a Conditional Variational Auto-Encoder (CVAE) to not only detect wildfires but also describe the stochasticity of the phenomenon and be capa-ble of running “what-if’ scenarios. Our proposed model is compatible with training on quantum computers, which re-sults in a quantum-assisted image-to-image segmentation approach and can be used to benchmark the potential benefit of quantum computing over the classical one.

The problem of compiling general quantum algorithms for implementation on near-term quantum processors has been introduced to the AI community. Previous work demonstrated that temporal planning is an attractive approach for part of this compilationtask, specifically, the routing of circuits that implement the Quantum Alternating Operator Ansatz (QAOA) applied to the MaxCut problem on a quantum processor architecture. In this paper, we extend the earlier work to route circuits that implement QAOA for Graph Coloring problems. QAOA for coloring requires execution of more, and more complex, operations on the chip, which makes routing a more challenging problem. We evaluate the approach on state-of-the-art hardware architectures from leading quantum computing companies. Additionally, we apply a planning approach to qubit initialization. Our empirical evaluation shows that temporal planning compares well to reasonable analytic upper bounds, and that solving qubit initialization with a classical planner generally helps temporal planners in finding shorter-makespan compilations for QAOA for Graph Coloring. These advances suggest that temporal planning can be an effective approach for more complex quantum computing algorithms and architectures.

Recent progress in quantum algorithms and hardware indicates the potential importance of quantum computing in the near future. However, finding suitable application areas remains an active area of research. Quantum machine learning is touted as a potential approach to demonstrate quantum advantage within both the gate-model and the adiabatic schemes. For instance, the Quantum-assisted Variational Autoencoder (QVAE) has been proposed as a quantum enhancement to the discrete VAE. We extend on previous work and study the real-world applicability of a QVAE by presenting a proof-of-concept for similarity search in large-scale high-dimensional datasets. While exact and fast similarity search algorithms are available for low dimensional datasets, scaling to high-dimensional data is non-trivial. We show how to construct a space-efficient search index based on the latent space representation of a QVAE. Our experiments show a correlation between the Hamming distance in the embedded space and the Euclidean distance in the original space on the Moderate Resolution Imaging Spectroradiometer (MODIS) dataset.Further, we find real-world speedups compared to linear search and demonstrate memory-efficient scaling to half a billion data points.

We present the mapping of a class of simplified air traffic management problems (strategic conflict resolution) to quadratic unconstrained Boolean optimization problems. The mapping is performed through an original representation of the conflict-resolution problem in terms of a conflict graph, where the nodes of the graph represent flights and the edges represent a potential conflict between flights. The representation allows a natural decomposition of a real-world instance related to wind-optimal trajectories over the Atlantic Ocean into smaller subproblems that can be discretized and are amenable to be programmed in quantum annealers. In this paper, we tested the new programming techniques, and we benchmark the hardness of the instances using both classical solvers and the D-Wave 2X and D-Wave 2000Q quantum chip. The preliminary results show that for reasonable modeling choices, the most challenging subproblems which are programmable in the current devices are solved to optimality with 99% of probability within a second of annealing time.

We investigate the application of temporal planners to the problem of compiling quantum circuits to emerging quantum hardware. While our approach is general, we focus our initial experiments on Quantum Approximate Optimization Algorithm (QAOA) circuits that have few ordering constraints and thus allow highly parallel plans. We report on experiments using several temporal planners to compile circuits of various sizes to a realistic hardware architecture. This early empirical evaluation suggests that temporal planning is a viable approach to quantum circuit compilation.

We consider a distributed private data analysis setting, where multiple parties each hold some sensitive data and they wish to run a protocol to learn some aggregate statistics over the distributed dataset, while protecting each user’s privacy. As an initial effort, we consider a distributed summation problem. We first show a lower bound, that is, under information-theoretic differential privacy, any multi-party protocol with a small number of messages must have large additive error. We then show that by adopting a computational differential privacy notion, one can circumvent this lower bound and design practical protocols for the periodic distributed summation problem. Our construction has several desirable features. First, it works in the client-server model and requires no peer-to-peer communication among the clients. Second, our protocol is fault tolerant and can output meaningful statistics even when a subset of the participants fail to respond. Our constructions guarantee the privacy of honest parties even when a fraction of the participants may be compromised and colluding. In addition, we propose a new distributed noise addition mechanism that guarantees small total error.

An effective approach to solving complex problems is to decompose them and integrate dedicated solvers for those subproblems. We introduce a hybrid decomposition that incorporates: (1) a quantum annealer that samples from the configuration space of a relaxed problem to obtain strong candidate solutions, and (2) a classical processor that maintains a global search tree and enforces constraints on the relaxed components of the problem. Our framework is the first to use quantum annealing as part of a complete search. We consider variants of our approach with differing amounts of guidance from the quantum annealer. We empirically test our algorithm and compare the variants on problems from three scheduling domains: graph-coloring-type scheduling, simplified Mars Lander task scheduling, and airport runway scheduling. While we were only able to test on problems of small sizes, due to the limitation of currently available quantum annealing hardware, the empirical results show that results obtained from the quantum annealer can be used for more effective search node pruning and to improve node selection heuristics when compared to a standard classical approach.

There are two complementary ways to evaluate planning algorithms: performance on benchmark problems derived from real applications and analysis of performance on parametrized families of problems with known properties. Prior to this work, few means of generating parametrized families of hard planning problems were known. We generate hard planning problems from the solvable/unsolvable phase transition region of well-studied NP-complete problems that map naturally to navigation and scheduling, aspects common to many planning domains. We observe significant differences between state-of-the-art planners on these problem families, enabling us to gain insight into the relative strengths and weaknesses of these planners. Our results confirm exponential scaling of hardness with problem size, even at very small problem sizes. These families provide complementary test sets exhibiting properties not found in existing benchmarks.

Affect influences workplace collaboration and thereby impacts a workplace's productivity. Participants in face-to-face interactions have many cues to each other's affect, but work is increasingly carried out via computer-mediated channels that lack many of these cues. Current presence systems enable users to estimate the availability of other users, but not their affective states or communication preferences. This work demonstrates the feasibility of estimating affective state and communication preferences from a stream of presence states that are already being shared in a deployed presence system.

Virtual, mobile, and mixed reality systems have diverse uses for data visualization and remote collaboration in industrial settings, especially factories. We report our experiences in designing complex mixed-reality collaboration, control, and display systems for a real-world factory, for delivering real-time factory information to multiple types of users. In collaboration with TCHO, a chocolate maker in San Francisco, our research group is building a virtual "mirror" world of a real-world chocolate factory and its processes. Sensor data is imported into the multi-user 3D environment from hundreds of sensors on the factory floor. The resulting "virtual factory" is designed for simulation, visualization, and collaboration, using a set of interlinked, real-time layers of information about the factory and its processes. We are also looking at appropriate industrial uses for mobile devices such as cell phones and tablet computers, and how they intersect with virtual worlds and mixed realities. For example, an experimental iPhone web app provides mobile laboratory monitoring and control. The mobile system is integrated with the database underlying the virtual factory world. These systems were deployed at the real-world factory and lab in 2009, and are now in beta development. Through this mashup of mobile, social, mixed and virtual technologies, we hope to create industrial systems for enhanced collaboration between physically remote people and places - for example, factories in China with managers in Japan or the US.

We propose an Augmented Reality (AR) system that helps users take a picture from a designated pose, such as the position and camera angle of an earlier photo. Repeat photography is frequently used to observe and document changes in an object. Our system uses AR technology to estimate camera poses in real time. When a user takes a photo, the camera pose is saved as a “view bookmark”. To support a user in taking a repeat photo, two simple graphics are rendered in an AR viewer on the camera's screen to guide the user to this bookmarked view. The system then uses image adjustment techniques to create an image based on the user's repeat photo that is even closer to the original.

We show several aspects of a complex mixed reality system that we have built and deployed in a real-world factory setting. In our system, virtual worlds, augmented realities, and social and mobile applications are all fed from the same infrastructure. In collaboration with TCHO[1], a chocolate maker in San Francisco, we built a virtual "mirror" world of a real-world chocolate factory and its processes. Sensor data is imported into the multi-user 3D environment from hundreds of sensors on the factory floor. The resulting virtual factory is used for simulation, visualization, and collaboration, using a set of interlinked, real-time layers of information. Another part of our infrastructure is designed to support appropriate industrial uses for mobile devices such as cell phones and tablet computers. We deployed this system at the real-world factory in 2009, and it is now is daily use there. By simultaneously developing mobile, virtual, and web-based display and collaboration environments, we aimed to create an infrastructure that did not skew toward one type of application but that could serve many at once, interchangeably. Through this mixture of mobile, social, mixed and virtual technologies, we hope to create systems for enhanced collaboration in industrial settings between physically remote people and places, such as factories in China with managers in the US.

In this paper, we describe an automatic lighting adjustment method for browsing object images. From a set of images of an object, taken under different lighting conditions, we generate two types of illuminated images: a textural image which eliminates unwanted specular reflections of the object, and a highlight image in which specularities of the object are highly preserved. Our user interface allows viewers to digitally zoom into any region of the image, and the lighting adjusted images are automatically generated for the selected region and displayed. Switching between the textural and the highlight images helps viewers to understand characteristics of the object surface.

The Pantheia system enables users to create virtual models by `marking up' the real world with pre-printed markers. The markers have predefined meanings that guide the system as it creates models. Pantheia takes as input user captured images or video of the marked up space. This video illustrates the workings of the system and shows it being used to create three models, one of a cabinet, one of a lab, and one of a conference room. As part of the Pantheia system, we also developed a 3D viewer that spatially integrates a model with images of the model.

This video shows the Virtual Physics Circus, a kind of playground for experimenting with simple physical models. The system makes it easy to create worlds with common physical objects such as swings, vehicles, ramps, and walls, and interactively play with those worlds. The system can be used as a creative art medium as well as to gain understanding and intuition about physical systems. The system can be controlled by a number of UI devices such as mouse, keyboard, joystick, and tags which are tracked in 6 degrees of freedom.

Wireless networking is widespread in public places such as cafes. Unsuspecting users may become victims of attacks based on "evil twin" access points. These rogue access points are operated by criminals in an attempt to launch man-in-the-middle attacks. We present a simple protection mechanism against binding to an evil twin. The mechanism leverages short authentication string protocols for the exchange of cryptographic keys. The short string verification is performed by encoding the short strings as a sequence of colors, rendered sequentially by the user's device and by the designated access point of the cafe. The access point must have a light capable of showing two colors and must be mounted prominently in a position where users can have confidence in its authenticity. We conducted a usability study with patrons in several cafes and participants found our mechanism very usable.

Our featured wand, automatically tracked by video cameras, provides an inexpensive and natural way for users to input 3D data or interact with devices such as large displays. The wand supports six degrees of freedom for manipulation of 3D applications like Google Earth. Our system uses a 'line scan' to estimate the wand pose tracking which simplifies processing. Several applications are demonstrated.

DOTS (Dynamic Object Tracking System) is an indoor, real-time, multi-camera surveillance system, deployed in a real office setting. DOTS combines video analysis and user interface components to enable security personnel to effectively monitor views of interest and to perform tasks such as tracking a person. The video analysis component performs feature-level foreground segmentation with reliable results even under complex conditions. It incorporates an efficient greedy-search approach for tracking multiple people through occlusion and combines results from individual cameras into multi-camera trajectories. The user interface draws the users. attention to important events that are indexed for easy reference at a later time. Different views within the user interface provide spatial information for easier navigation. Our system, with over twenty video cameras installed in hallways and other public spaces in our office building, has been in constant use for almost a year.

We present a general approach to temporal media segmentation using supervised classification. Given standard low-level features representing each time sample, we build intermediate features via pairwise similarity. The intermediate features comprehensively characterize local temporal structure, and are input to an efficient supervised classifier to identify shot boundaries. We integrate discriminative feature selection based on mutual information to enhance performance and reduce processing requirements. Experimental results using large-scale test sets provided by the TRECVID evaluations for abrupt and gradual shot boundary detection are presented, demonstrating excellent performance

MOTIVATION: Expressed sequence tag (EST) data reflects variation in gene expression, but previous methods for finding coexpressed genes in EST data are subject to bias and vastly overstate the statistical significance of putatively coexpressed genes. RESULTS: We introduce a new method (LNP) that reports reasonable p-values and also detects more biological relationships in human dbEST than do previous methods. In simulations with human dbEST library sizes, previous methods report p-values as low as 10(-30) on 1/1000 uncorrelated pairs, while LNP reports significance correctly. We validate the analysis on real human genes by comparing coexpressed pairs to gene ontology annotations and find that LNP is more sensitive than the three previous methods. We also find a small but statistically significant level of coexpression between interacting proteins relative to randomized controls. The LNP method is based on a log-normal prior on the distribution of expression levels.

This work extends previous research on developing control software for modular robotic smart membranes to a second module type with more complicated movement, to 3-D membranes, to the presence of gravity, and to less easily manipulatable objects. Moreover, it extends the capabilities of the membranes from simple filtering to more complex sorting tasks. The control software we developed is completely decentralized, and automatically generated.

We discuss the theoretical limitations for reconfiguration of metamorphic robots made up of Telecubes, six degree of freedom cube shaped modules currently being developed at Xerox PARC. We show that by using meta-modules composed of 8 individual modules as a backbone for building the desired shape, we can establish completeness for the reconfiguration as well as time and space bounds for the process. Finally we present several open problems in the field of reconfiguration.