Simulating quantum channels is a fundamental primitive in quantum computing, since quantum channels define general (trace-preserving) quantum operations. An arbitrary quantum channel cannot be exactly simulated using a finite-dimensional programmable quantum processor, making it important to develop optimal approximate simulation techniques. In this paper, we study the challenging setting in which the channel to be simulated varies adversarially with time. We propose the use of matrix exponentiated gradient descent (MEGD), an online convex optimization method, and analytically show that it achieves a sublinear regret in time. Through experiments, we validate the main results for time-varying dephasing channels using a programmable generalized teleportation processor.
Simulating quantum channels is a fundamental primitive in quantum computing, since quantum channels define general (trace-preserving) quantum operations. An arbitrary quantum channel cannot be exactly simulated using a finite-dimensional programmable quantum processor, making it important to develop optimal approximate simulation techniques. In this paper, we study the challenging setting in which the channel to be simulated varies adversarially with time. We propose the use of matrix exponentiated gradient descent (MEGD), an online convex optimization method, and analytically show that it achieves a sublinear regret in time. Through experiments, we validate the main results for time-varying dephasing channels using a programmable generalized teleportation processor.
Abstract A fundamental model of quantum computation is the programmable quantum gate array. This is a quantum processor that is fed by a program state that induces a corresponding quantum operation on input states. While being programmable, any finite-dimensional design of this model is known to be nonuniversal, meaning that the processor cannot perfectly simulate an arbitrary quantum channel over the input. Characterizing how close the simulation is and finding the optimal program state have been open questions for the past 20 years. Here, we answer these questions by showing that the search for the optimal program state is a convex optimization problem that can be solved via semidefinite programming and gradient-based methods commonly employed for machine learning. We apply this general result to different types of processors, from a shallow design based on quantum teleportation, to deeper schemes relying on port-based teleportation and parametric quantum circuits.
As a fundamental tool in AI, convex optimization has been a significant research field for many years, and the same goes for its online version. Recently, general convex optimization problem has been accelerated with the help of quantum computing, and the technique of online convex optimization has been used for accelerating the online quantum state learning problem, thus we want to study whether online convex optimization (OCO) model can also be benefited from quantum computing. In this paper, we consider the OCO model, which can be described as a T round iterative game between the player and the adversary. A key factor for measuring the performance of an OCO algorithm A is the regret denoted by regretT(A), and it is said to perform well if its regret is sublinear as a function of T. Another factor is the computational cost (e.g., query complexity) of the algorithm. We give a quantum algorithm for the online convex optimization model with only zeroth-order oracle available, which can achieve O(T) and O(logT) regret for general convex loss functions and α-strong loss functions respectively, where only O(1) queries are needed in each round. Our results show that the zeroth-order quantum oracle is as powerful as the classical first-order oracle, and show potential advantages of quantum computing over classical computing in the OCO model where only zeroth-order oracle available.
Abstract We explore whether quantum advantages can be found for the zeroth-order online convex optimization (OCO) problem, which is also known as bandit convex optimization with multi-point feedback. In this setting, given access to zeroth-order oracles (that is, the loss function is accessed as a black box that returns the function value for any queried input), a player attempts to minimize a sequence of adversarially generated convex loss functions. This procedure can be described as a T round iterative game between the player and the adversary. In this paper, we present quantum algorithms for the problem and show for the first time that potential quantum advantages are possible for problems of OCO. Specifically, our contributions are as follows. (i) When the player is allowed to query zeroth-order oracles O (1) times in each round as feedback, we give a quantum algorithm that achieves O ( T ) regret without additional dependence of the dimension n , which outperforms the already known optimal classical algorithm only achieving O ( n T ) regret. Note that the regret of our quantum algorithm has achieved the lower bound of classical first-order methods. (ii) We show that for strongly convex loss functions, the quantum algorithm can achieve O (log T ) regret with O (1) queries as well, which means that the quantum algorithm can achieve the same regret bound as the classical algorithms in the full information setting.
Quantum simulation, which is generically the task to employ quantum computers to simulate quantum physical models, has been one of the most significant motivations of quantum computing. Quantum dynamics, unitary or nonunitary Markovian dynamics driven by local interactions, has been proved to be efficiently simulatable on quantum computers. Extending the underlying models from unitary to nonunitary evolution, and from continuous-time to discrete-time evolution is essential not only for quantum simulation of more general processes, e.g., dissipative processes with evident non-Markovian effects, but also for developing alternative quantum computing models and algorithms. In this thesis, we explore quantum simulation problems mainly from the following three themes. First, we extend quantum simulation framework of Hamiltonian-driven evolution to quantum simulation of quantum channels, combined with the scheme of algorithmic simulation that accepts a promised simulation accuracy, hence algorithmic quantum channel simulation. Our simulation scheme contains a classical preprocessing part, i.e. a classical algorithm for quantum-circuit design, and a quantum part that is the execution of a quantum circuit for the quantum channel simulator. Second, we employ simulation algorithms for arbitrary quantum channels beyond the dilation method. We explore channel decomposition in terms of convex combination of smaller channels, known as generalized extreme channels, which is known as a nontrivial open problem. To attack this problem, we develop an optimization algorithm for approximate decomposition into a convex sum of generalized extreme channels. We provide an ansatz that proves to be able to yield arbitrary generalized extreme channels and allows a precise quantum circuit description. Furthermore, our numerical simulation has demonstrated the validity of our optimization algorithm for low-dimensional quantum channels. Third, by considering quantum simulation problems beyond the rough distinction between digital and analog simulations, and beyond the quantum-state generation problem, we define uniform, strong, and weak quantum simulations from the point view of operator topology. Besides strong simulation of quantum channels, we define a general weak quantum simulation problem, which simulates observable effects instead of the effects on state generation. Also we study the channel simulation problem in the quantum query model, and provide the query complexity by employing uniform quantum simulation method.
Quantum computers still suffer from errors that keep them in the category of Noisy Intermediate-Scale Quantum (NISQ) computers. Among the various tools capable of circumventing some of the problems of NISQ computers, there is the Variational Quantum Algorithm (VQA). This algorithm can be useful in almost all sub-areas of quantum computing, such as error correction, compilation, combinatorial optimization, and dynamic simulations. These algorithms involve optimization processes in parametric rotation gates and can make use of well-founded optimizers in classical machine learning in computing. Some studies in the formalism of quantum mechanics lead us to possible experiments on a quantum computer, but due to its sensitivity, these experiments require daily calibration. When dealing with an external environment, the system behaves as an open system, governed by a unitary operator in the global state space and described by a completely positive trace-preserving map (CPTP) in the local state space. We call these processes quantum channels, which result in an evolved state over time. Through the formalism of the representation in terms of Kraus operators, we obtain the evolved states through analytical calculations and compare the coherence of this state with the coherence of the evolved state obtained through the protocol of simulating noisy quantum channels proposed in [M. S. Zanetti, D. F. Pinto, M. L. W. Basso, and J. Maziero, Simulating noisy quantum channels via quantum state preparation algorithms, J. Phys. B: At. Mol. Opt. Phys. 56, 115501 (2023)]. During a step of this protocol, state preparations are performed using functions from the Qiskit library. The present work performs state preparations using VQA. We simulate channels associated with bit-flip, phase-flip, bit-phase-flip, depolarizing, amplitude damping, phase damping, generalized amplitude damping, Lorentz, and Heisenberg-Weyl dephasing. The results of simulations with VQA are satisfactory, with the coherence of the simulated state approaching the analytical value. This demonstrates the usefulness of VQA in state preparation for this problem.
Among recent insights into learning quantum states, online learning and shadow tomography procedures are notable for their ability to accurately predict expectation values even of adaptively chosen observables. In contrast to the state case, quantum process learning tasks with a similarly adaptive nature have received little attention. In this work, we investigate online learning tasks for quantum processes. Whereas online learning is infeasible for general quantum channels, we show that channels of bounded gate complexity as well as Pauli channels can be online learned in the regret and mistake-bounded models of online learning. In fact, we can online learn probabilistic mixtures of any exponentially large set of known channels. We also provide a provably sample-efficient shadow tomography procedure for Pauli channels. Our results extend beyond quantum channels to non-Markovian multi-time processes, with favorable regret and mistake bounds, as well as a shadow tomography procedure. We complement our online learning upper bounds with mistake as well as computational lower bounds. On the technical side, we make use of the multiplicative weights update algorithm, classical adaptive data analysis, and Bell sampling, as well as tools from the theory of quantum combs for multi-time quantum processes. Our work initiates a study of online learning for classes of quantum channels and, more generally, non-Markovian quantum processes. Given the importance of online learning for state shadow tomography, this may serve as a step towards quantum channel variants of adaptive shadow tomography.