Parameterized Quantum Circuit (PQC) is a family of structured quantum circuits that consists of quantum gates whose parameters are optimized with classical computers. With the quest for a potential speedup, there is a need to run larger quantum circuits, which in turn results in the arduous task of parameter optimization. In this paper, we propose a generic method, called Rotolasso, that utilizes sparsity-inducing coordinate descent (CD) to optimize parameters of a PQC for balancing its accuracy and the number of parameterized gates. The use of CD allows significant reduction in the number of quantum circuit runs, and the sparsity in the model leads to simpler and faster PQCs, both of which are important ingredients to overcome limitations of near-term quantum devices. We provide theoretical analyses and demonstrate experiments showing the effectiveness of Rotolasso to solve instances of combinatorial optimization problems.

Variational quantum algorithm (VQA) is a promising near-term quantum algorithm to efficiently generate quantum states for various applications from shallow parametrized quantum circuits (PQCs). To fully utilize VQA, it is essential to have measurement methods that efficiently extract desired information from the quantum states. Classical shadow is such method that measures each qubit onto one of three Pauli bases uniformly at random. It has been attracting active research for characterizing the quantum states of PQCs due to its requiring only polynomial number of measurements, in the number of qubits, in contrast to the exponential-measurement quantum state tomography. There are several variants of classical shadow to improve the accuracy of measurement. A highly accurate classical shadow whose choices of Pauli bases are based on a decision diagram (DD) has been recently proposed in designing PQCs. Here, we further extend the DD-based classical shadow by novel modification and application of conventional techniques to optimize DD. We develop a method to optimize the size of DD that can lead to even fewer number of measurements for optimization instances in quantum chemistry as confirmed by numerical experiments. Our results show another facet of the usefulness of DD in the design of PQCs.

Quantum Approximate Optimization Algorithm (QAOA) is one of the most promising quantum heuristics for combinatorial optimization. While QAOA has been shown to perform well on small-scale instances and to provide an asymptotic speedup over state-of-the-art classical algorithms for some problems, fault-tolerance is understood to be required to realize this speedup in practice. The low resource requirements of QAOA make it particularly suitable to benchmark on early fault-tolerant quantum computing (EFTQC) hardware. However, the performance of QAOA depends crucially on the choice of the free parameters in the circuit. The task of setting these parameters is complicated in the EFTQC era by the large overheads, which preclude extensive classical optimization. In this paper, we summarize recent advances in parameter setting in QAOA and show that these advancements make EFTQC experiments with QAOA practically viable.

Quantum classifiers provide sophisticated embeddings of input data in Hilbert space promising quantum advantage. The advantage stems from quantum feature maps encoding the inputs into quantum states with variational quantum circuits. A recent work shows how to map discrete features with fewer quantum bits using Quantum Random Access Coding (QRAC) to encode binary strings into quantum states. We propose a new method to embed discrete features with trainable quantum circuits by combining QRAC and a recently proposed strategy for training quantum feature map called quantum metric learning. The proposed trainable embedding requires not only as few qubits as QRAC but also overcomes the limitations of QRAC to classify inputs whose classes are based on hard Boolean functions. We numerically demonstrate its use in variational quantum classifiers to achieve better performances to classify real-world datasets, and thus its possibility to use near-term quantum computers for machine learning.

Due to the significant progress made in the implementation of quantum hardware, efficient methods and tools to design corresponding algorithms become increasingly important. Many of these tools rely on functional representations of certain building blocks or even entire quantum algorithms which, however, inherently exhibit an exponential complexity. Although several alternative representations have been proposed to cope with this complexity, the construction of those representations remains a bottleneck. In this work, we propose solutions for efficiently constructing representations of quantum functionality based on the idea of conducting as many operations as possible on as small as possible intermediate representations -- using Decision Diagrams as a representative functional description. Experimental evaluations show that applying these solutions allows to construct the desired representations several factors faster than with state-of-the-art methods. Moreover, if repeating structures (which frequently occur in quantum algorithms) are explicitly exploited, exponential improvements are possible -- allowing to construct the functionality of certain algorithms within seconds, whereas the state of the art fails to construct it in an entire day.

We propose a task called Visual Concept Naming to associate visual concepts with the corresponding textual expressions, i.e., names of visual concepts found in real-world multimodal data. To tackle the task, we create a dataset consisting of 3.4 million tweets in total in three languages. We also propose a method for extracting candidate names of visual concepts and validating them by exploiting Web-based knowledge obtained through image search. To demonstrate the capability of our method, we conduct an experiment with the dataset we create and evaluate names obtained by our method through crowdsourcing, where we establish an evaluation method to verify the names. The experimental results indicate that the proposed method can identify a wide variety of names of visual concepts. The names we obtained also show interesting insights regarding languages and countries where the languages are used.1

We study reinforcement learning for controlling multiple agents in a collaborative manner. In some of those tasks, it is insufficient for the individual agents to take relevant actions, but those actions should also have diversity. We propose the approach of using the determinant of a positive semidefinite matrix to approximate the action-value function in reinforcement learning, where we learn the matrix in a way that it represents the relevance and diversity of the actions. Experimental results show that the proposed approach allows the agents to learn a nearly optimal policy approximately ten times faster than baseline approaches in benchmark tasks of multi-agent reinforcement learning. The proposed approach is also shown to achieve the performance that cannot be achieved with conventional approaches in partially observable environment with exponentially large action space.

The use of noisy intermediate-scale quantum computers (NISQCs), which consist of dozens of noisy qubits with limited coupling constraints, has been increasing. A circuit compiler, which transforms an input circuit into an equivalent output circuit conforming the coupling constraints with as few additional gates as possible, is essential for running applications on NISQCs. We propose a formulation and two algorithms exploiting gate commutation rules to obtain a better circuit compiler.

Quantum computing simulation on a classical computer is difficult due to the exponential runtime and memory overhead. Previous work addresses the difficulty by utilizing multiple Graphical Processing Units (GPUs) and multi-node computers. GPUs are efficient for handling runtime issues but have limited total accessible memory space. Meanwhile, the memory of a multi-node computer can be scaled to the petabytes order, but its bandwidth for access from host computers (CPUs) is narrow. To simultaneously accelerate simulation and enlarge the total memory space, we propose a heterogeneous parallelization approach by combining GPUs and CPUs. Our simulator allocates memory to the GPUs first, and then to the CPUs. It thus accelerates simulation by using the full capabilities of the GPUs if memory for the simulation fits in the GPUs on a cluster. Allocating memory to the CPUs reduces benefits of the GPUs but enlarges the capacity of qubits in the simulation. In such case, it can exploit the memory of the GPUs to add one more qubit in the simulation if the size of memory in a node is the power of two (such as 512GB). We show empirical performance evaluations of our simulator in a distributed environment of POWER9.

This paper is concerned with the task of collaborative density estimation in the distributed multi-task setting. Major application scenarios include collaborative anomaly detection among distributed industrial assets owned by different companies competing with each other. Of critical importance here is to achieve two conflicting goals at once: data privacy and collaboration. To this end, we propose a new framework for collaborative dictionary learning. By using a mixture of the exponential family, we show that collaborative learning can be nicely separated into three steps: local updates, global consensus, and optimization. For the critical step of consensus building, we propose a new algorithm that does not rely on expensive encryption-based multi-party computation. Our theoretical and experimental analysis shows that our method is several orders of magnitude faster than the alternative.

The determinantal point process (DPP) has been receiving increasing attention in machine learning as a generative model of subsets consisting of relevant and diverse items. Recently, there has been a significant progress in developing efficient algorithms for learning the kernel matrix that characterizes a DPP. Here, we propose a dynamic DPP, which is a DPP whose kernel can change over time, and develop efficient learning algorithms for the dynamic DPP. In the dynamic DPP, the kernel depends on the subsets selected in the past, but we assume a particular structure in the dependency to allow efficient learning. We also assume that the kernel has a low rank and exploit a recently proposed learning algorithm for the DPP with low-rank factorization, but also show that its bottleneck computation can be reduced from O(M2 K) time to O(M K2) time, where M is the number of items under consideration, and K is the rank of the kernel, which can be set smaller than M by orders of magnitude.

We study the problem of identifying vehicle trajectories from the sequences of noisy geospatial-temporal datasets. Nowadays we witness the accumulation of vehicle trajectory datasets in the form of the sequences of GPS points. However, in many cases the sequences of GPS points are sparse and noisy so that identifying the actual trajectories of vehicles is hard. Although there are many advanced map-matching techniques claiming to achieve high accuracy to deal with the problem, only few public datasets that come with ground truth trajectories for supporting the claims. On the other hand, some cities are releasing their bus datasets for real-time monitoring and analytics. Since buses are expected to run on predefined routes, such datasets are highly valuable for map-matching and other pattern recognition applications. Nevertheless, some buses in reality appear not following their predefined routes and behave anomalously. We propose a simple and robust technique based on the combination of map-matching, bag-of-roads, and dimensionality reduction for their route identification. Experiments on datasets of buses in the city of Rio de Janeiro confirm the high accuracy of our method.

We propose a solution to a new problem that is faced by steelworks, who own private thermal power-plants and plan to use batteries to absorb fluctuations in power demand. A major challenge is in controlling both the power generation and the use of batteries under such fluctuations. We formulate a Markov decision process (MDP) and design the states of the MDP so that it has a periodic structure to avoid the explosion of its state space. We then develop a policy iteration algorithm that exploits the periodic structure for computational efficiency. Numerical experiments suggest that the combination of the proposed MDP and the policy iteration allows us to find a control policy that can significantly reduce the electricity cost.

The difficulty in allocating virtual machines (VMs) on servers stems from the requirement that sufficient resources (such as CPU capacity and network bandwidth) must be available for each VM in the event of a failure or maintenance work as well as for temporal fluctuations of resource demands, which often exhibit periodic patterns. We propose a mixed integer programming approach that considers the fluctuations of the resource demands for optimal and dependable allocation of VMs. At the heart of the approach are techniques for optimally partitioning the time-horizon into intervals of variable lengths and for reliably estimating the resource demands in each interval. We show that our new approach allocates VMs successfully in a cloud computing environment in a financial company, where the dependability requirement is strict and there are various types of VMs exist.

Bounds on performance of a queueing model can provide useful information to guarantee quality of service for communication networks. We study the bounds on the mean delay in a transient GI/GI/1 queue given the first two moments of the service time and the inter-arrival time, respectively. We establish a simple upper-bound, which then is used to show that the true transient mean-delay is at most four times larger than an asymptotic diffusion-approximation. We also prove that the tight lower-bound is zero as long as the service time and the inter-arrival time have finite variance and the load is below one. Tightness of the trivial lower-bound is in contrast to the stationary mean-delay, which has strictly positive lower-bound when the service time is sufficiently variable. We also show how our results can be applied to analyze the transient mean delay of packets in the real-world Internet.

An on-demand bus is like a shared taxi that operates only when riders want to travel between the origin and destination locations. It offers many advantages over fixed-route buses, but the riders are bothered by the need to tediously enter such data as origins, destinations, and deadlines. A location recommendation system that predicts such data would help riders during the reservation process and help target potential riders when buses are idle. In this paper, a general and scalable framework for such location recommendation algorithms is presented. It is based on users' location histories and spatio-temporal correlations among the locations by combining prediction methods of the collaborative filtering algorithms, which are widely used in e-commerce, with a popular method in data mining called link propagation. Experiments on real-world data demonstrate that the accuracy of recommendations with the spatio-temporal information is better than those without.

We derive an upper bound on the tail distribution of the transient waiting time for the GI/GI/1 queue from a formulation of semidefinite programming (SDP). Our upper bounds are expressed in closed forms using the first two moments of the service time and the interarrival time. The upper bounds on the tail distributions are integrated to obtain the upper bounds on the corresponding expectations. We also extend the formulation of the SDP, using the higher moments of the service time and the interarrival time, and calculate upper bounds and lower bounds numerically.

An (n,1,p)-quantum random access (QRA) coding, introduced by Ambainis, Nayak, Ta-shma and Vazirani in ACM Symp. on Theory of Computing 1999, is the following communication system: The sender which has n-bit information encodes his/her information into one qubit, which is sent to the receiver. The receiver can recover any one bit of the original n bits correctly with probability at least p, through a certain decoding process based on positive operator-valued measures. Actually, Ambainis et al. shows the existence of a (2,1,0.85)-QRA coding and also proves the impossibility of its classical counterpart. Chuang immediately extends it to a (3,1,0.79)-QRA coding and whether or not a (4,1,p)-QRA coding such that p > 1/2 exists has been open since then. This paper gives a negative answer to this open question