Best arm identification (BAI) is a key problem in stochastic multi-armed bandits, where K arms each has an associated reward distribution, and the objective is to minimize the number of queries needed to identify the best arm with high confidence. In this paper, we explore BAI using quantum oracles. For the case where each query probes only one arm (m=1), we devise a quantum algorithm with a query complexity upper bound of O((K/Delta)log(1/delta)), where delta is the confidence parameter and Delta is the reward gap between best and second best arms. This improves on the classical bound by a factor of 1/Delta. For the general case where a single query can probe m arms (1

In this work, we initiate a systematic study of the time complexity of quantum divide and conquer (QD&C) algorithms for classical problems, and propose a general framework for their analysis. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup, and apply these theorems to various problems involving strings, integers, and geometric objects. These include Longest Distinct Substring, Klee's Coverage, several optimization problems on stock transactions, and k-Increasing Subsequence. For most of these problems our quantum time upper bounds match the quantum query lower bounds, up to polylogarithmic factors. We give a structured framework for describing and classifying a wide variety of QD&C algorithms so that quantum speedups can be more easily identified and applied, and prove general statements on QD&C time complexity covering a range of cases, accounting for the time required for all operations. In particular, we explicitly account for memory access operations in the commonly used QRAM (read-only) and QRAG (read-write) models, which are assumed to take unit time in the query model, and which require careful analysis when involved in recursion. Our generic QD&C theorems have several nice features. 1) To apply them, it suffices to come up with a classical divide and conquer algorithm satisfying the conditions of the theorem. The quantization of the algorithm is then completely handled by the theorem. This can make it easier to find applications which admit a quantum speedup, and contrast with dynamic programming algorithms which can be difficult to quantize due to their highly sequential nature. 2) As these theorems give bounds on time complexity, they can be applied to a greater range of problems than those based on query complexity, e.g., where the best-known quantum algorithms require super-linear time. 3) It can handle minimization problems as well as boolean functions, which allows us to improve on the query complexity result of Childs et al. [Childs et al., 2025] for k-Increasing Subsequence by a logarithmic factor.

In this work, we design quantum algorithms that are more efficient than classical algorithms to solve time-dependent and finite-horizon Markov Decision Processes (MDPs) in two distinct settings: (1) In the exact dynamics setting, where the agent has full knowledge of the environment’s dynamics (i.e., transition probabilities), we prove that our Quantum Value Iteration (QVI) algorithm QVI-1 achieves a quadratic speedup in the size of the action space $(A)$ compared with the classical value iteration algorithm for computing the optimal policy ($\pi^{\ast}$) and the optimal V-value function ($V_{0}^{\ast}$). Furthermore, our algorithm QVI-2 provides an additional speedup in the size of the state space $(S)$ when obtaining near-optimal policies and V-value functions. Both QVI-1 and QVI-2 achieve quantum query complexities that provably improve upon classical lower bounds, particularly in their dependences on $S$ and $A$. (2) In the generative model setting, where samples from the environment are accessible in quantum superposition, we prove that our algorithms QVI-3 and QVI-4 achieve improvements in sample complexity over the state-of-the-art (SOTA) classical algorithm in terms of $A$, estimation error $(\epsilon)$, and time horizon $(H)$. More importantly, we prove quantum lower bounds to show that QVI-3 and QVI-4 are asymptotically optimal, up to logarithmic factors, assuming a constant time horizon.

Large-scale quantum networks with thousands of nodes require topology-oblivious routing protocols to realize. Most existing quantum network routing protocols only consider the intra-domain scenario, where all nodes belong to a single party with complete topology knowledge. However, like the classical Internet, quantum Internet will likely be provided by multiple quantum Internet Service Providers (qISPs). In this paper, we consider the inter-domain scenario, where the network consists of multiple subnetworks owned by mutually untrusted parties without centralized control. Under this setting, previously proposed quantum entanglement routing policies, which rely on the network topology knowledge, are no longer applicable. We propose a Quantum Border Gateway Protocol (QBGP) for efficiently routing entanglement across qISP boundaries. To guarantee high-quality information transmission, we propose an algorithm named online top-K path selection. This algorithm utilizes the information gain introduced in this paper to adaptively decide on measurement parameters, allowing for the selection of high-fidelity paths and accurate fidelity estimates, while minimizing costs. Additionally, we implement a quantum network simulator and evaluate our protocol and algorithm. Our evaluation shows that QBGP effectively distributes entanglement across different qISPs, and our path selection algorithm increases the network performance by selecting high-fidelity paths with much lower resource consumption than other methods.

Coplanar Waveguides (CPW) are ideally suited for coherently interfacing resonators with superconducting qubits. However, integrating CPWs with circuit elements on quantum chips involves curvature and discontinuities of the central conductors and corresponding ground planes, which may generate undesired parasitic modes. Experiments have demonstrated that air-bridges can effectively suppress this unwanted effect. Nevertheless, as quantum processors increase in size, manual air-bridge placement on the chip layout becomes increasingly time-consuming and error-prone. Automation of this process is therefore highly desirable, especially when the center line (channel) of the CPWs is not pre-established. In this paper we propose a parametric EDA method for coplanar waveguide channel identification and air-bridge construction in quantum chips. Our approach applies to both separated and full-package air-bridges and scales efficiently, with running time linear in the number of points and quadratic in the number of arcs in the corresponding chip layout. We evaluate our approach on a set of open-source quantum chip layouts, generating air-bridges in times ranging from 0.05 to 0.5 seconds—a practical speedup of over 10,000 times compared to manual generation. Furthermore, We propose two original quantitative metrics, accuracy and overlap, and verify that our method yields reliable results, producing air-bridges in the required shapes and locations. We fabricate a 13-qubit chip using our method for air-bridge placement, and observe excellent performance with minimal microwave and flux crosstalk. This research enables rapid generation of air-bridges when CPW channels are not pre-specified, paving the way for more flexible, automated, and modular design of superconducting quantum EDA.

Some physical implementation schemes of quantum computing can apply two-qubit gates only on certain pairs of qubits. These connectivity constraints are commonly viewed as a significant disadvantage. For example, compiling an unrestricted$n$-qubit quantum circuit to one with poor qubit connectivity, such as a 1-D chain, usually results in a blowup of depth by$O(n^{2})$and size by$O(n)$. It is appealing to conjecture that this overhead is unavoidable—a random circuit on$n$qubits has$\Theta (n)$two-qubit gates in each layer and a constant fraction of them act on qubits separated by distance$\Theta (n)$. While it is known that almost all$n$-qubit unitary operations need quantum circuits of$\Omega (4^{n}/n)$depth and$\Omega (4^{n})$size to realize with all-to-all qubit connectivity, in this article, we show that all$n$-qubit unitary operations can be implemented by quantum circuits of$O(4^{n}/n)$depth and$O(4^{n})$size even under 1-D chain qubit connectivity constraint. We extend this result and investigate qubit connectivity in three directions. First, we consider more general connectivity graphs and show that the circuit size can always be made$O(4^{n})$as long as the graph is connected. For circuit depth, we study$d$-dimensional grids, complete$d$-ary trees and expander graphs, and show results similar to the 1-D chain. Second, we consider the case when ancillary qubits are available. We show that, with ancilla, the circuit depth can be made polynomial, and the space-depth trade-off is not impaired by connectivity constraints unless we have exponentially many ancillary qubits. Third, we obtain nearly optimal results on special families of unitaries, including diagonal unitaries, 2-by-2 block diagonal unitaries, and quantum state preparation (QSP) unitaries, the last being a fundamental task used in many quantum algorithms for machine learning and linear algebra.

Noise is a significant obstacle to quantum computing, and ZZ crosstalk is one of the most destructive types of noise affecting superconducting qubits. Previous approaches to suppressing ZZ crosstalk have mainly relied on specific chip design that can complicate chip fabrication and aggravate decoherence. To some extent, special chip design can be avoided by relying on pulse optimization to suppress ZZ crosstalk. However, existing approaches are non-scalable, as their required time and memory grow exponentially with the number of qubits involved.

International audience

Quantum machine learning has the potential for broad industrial applications, and the development of quantum algorithms for improving the performance of neural networks is of particular interest given the central role they play in machine learning today. We present quantum algorithms for training and evaluating feedforward neural networks based on the canonical classical feedforward and backpropagation algorithms. Our algorithms rely on an efficient quantum subroutine for approximating inner products between vectors in a robust way, and on implicitly storing intermediate values in quantum random access memory for fast retrieval at later stages. The running times of our algorithms can be quadratically faster in the size of the network than their standard classical counterparts since they depend linearly on the number of neurons in the network, and not on the number of connections between neurons. Furthermore, networks trained by our quantum algorithm may have an intrinsic resilience to overfitting, as the algorithm naturally mimics the effects of classical techniques used to regularize networks. Our algorithms can also be used as the basis for new quantum-inspired classical algorithms with the same dependence on the network dimensions as their quantum counterparts but with quadratic overhead in other parameters that makes them relatively impractical.