Distributed quantum computing (DQC) offers a pathway for scaling up quantum computing architectures beyond the confines of a single chip. Entanglement is a crucial resource for implementing nonlocal operations in DQC, and it is required to allow teleportation of quantum states and gates. Remote entanglement generation in practical systems is probabilistic, has longer duration than that of local operations, and is nondeterministic. Therefore, optimizing the performance of probabilistic remote entanglement generation is critically important for the performance of DQC architectures. In this paper we propose and study a new DQC architecture that combines (1) buffering of successfully generated entanglement, (2) asynchronously attempted entanglement generation, and (3) adaptive scheduling of remote gates based on the entanglement generation pattern. We show that our hardware-software co-design improves both the runtime and the output fidelity under a realistic model of DQC.

Due to the sparse connectivity of superconducting quantum computers, qubit communication via SWAP gates accounts for the vast majority of overhead in quantum programs. We introduce a method for improving the speed and reliability of SWAPs at the level of the superconducting hardware’s native gateset. Our method relies on four techniques: 1) SWAP Orientation, 2) Cross-Gate Pulse Cancellation, 3) Commutation through Cross-Resonance, and 4) Cross-Resonance Polarity. Importantly, our Optimized SWAP is bootstrapped from the pre-calibrated gates, and therefore incurs zero calibration overhead. We experimentally evaluate our optimizations with Qiskit Pulse on IBM hardware. Our Optimized SWAP is 11% faster and 13% more reliable than the Standard SWAP. We also experimentally validate our optimizations on application-level benchmarks. Due to (a) the multiplicatively compounding gains from improved SWAPs and (b) the frequency of SWAPs, we observe typical improvements in success probability of 10–40%. The Optimized SWAP is available through the Superstaq platform.

While quantum computing holds great potential in combinatorial optimization, electronic structure calculation, and number theory, the current era of quantum computing is limited by noisy hardware. Many quantum compilation approaches can mitigate the effects of imperfect hardware by optimizing quantum circuits for objectives such as critical path length. Few approaches consider quantum circuits in terms of the set of vendor-calibrated operations (i.e., native gates) available on target hardware. This manuscript expands the analytical and numerical approaches for optimizing quantum circuits at this abstraction level. We present a procedure for combining the strengths of analytical native gate-level optimization with numerical optimization. Although we focus on optimizing Toffoli gates on the IBMQ native gate set, the methods presented are generalizable to any gate and superconducting qubit architecture. Our optimized Toffoli gate implementation demonstrates an 18% reduction in infidelity compared with the canonical implementation as benchmarked on IBM Jakarta with quantum process tomography. Assuming the inclusion of multi-qubit cross-resonance (MCR) gates in the IBMQ native gate set, we produce Toffoli implementations with only six multi-qubit gates, a 25% reduction from the canonical eight multi-qubit implementations for linearly connected qubits.

Quantum computing (QC) is a new paradigm offering the potential of exponential speedups over classical computing for certain computational problems. Each additional qubit doubles the size of the computational state space available to a QC algorithm. This exponential scaling underlies QC’s power, but today’s Noisy Intermediate-Scale Quantum (NISQ) devices face significant engineering challenges in scalability. The set of quantum circuits that can be reliably run on NISQ devices is limited by their noisy operations and low qubit counts. This paper introduces CutQC, a scalable hybrid computing approach that combines classical computers and quantum computers to enable evaluation of quantum circuits that cannot be run on classical or quantum computers alone. CutQC cuts large quantum circuits into smaller subcircuits, allowing them to be executed on smaller quantum devices. Classical postprocessing can then reconstruct the output of the original circuit. This approach offers significant runtime speedup compared with the only viable current alternative—purely classical simulations—and demonstrates evaluation of quantum circuits that are larger than the limit of QC or classical simulation. Furthermore, in real-system runs, CutQC achieves much higher quantum circuit evaluation fidelity using small prototype quantum computers than the state-of-the-art large NISQ devices achieve. Overall, this hybrid approach allows users to leverage classical and quantum computing resources to evaluate quantum programs far beyond the reach of either one alone.

Quantum codes excel at correcting local noise but fail to correct leakage faults that excite qubits to states outside the computational space. Aliferis and Terhal have shown that an accuracy threshold exists for leakage faults using gadgets called leakage reduction units (LRUs). However, these gadgets reduce the threshold and increase experimental complexity, and the costs have not been thoroughly understood. We explore a variety of techniques for leakage resilience in topological codes. Our contributions are threefold. First, we develop a leakage model that is physically motivated and efficient to simulate. Second, we use Monte-Carlo simulations to survey several syndrome extraction circuits. Third, given the capability to perform 3-outcome measurements, we present a dramatically improved syndrome processing algorithm. Our simulations show that simple circuits with one extra CNOT per qubit reduce the accuracy threshold by less than a factor of 4 when leakage and depolarizing noise rates are comparable compared to a scenario without leakage. This becomes a factor of 2 when the decoder uses 3-outcome measurements. Finally, we make the surprising observation that for physical error rates less than 2 × 10-4, placing LRUs after every gate may achieve the lowest logical error rate. We expect that the ideas may generalize to other topological codes.

We describe QuRE, the Quantum Resource Estimator. QuRE is a layout estimation tool that estimates the cost of practical implementations of quantum circuits in a variety of competing physical quantum technologies and with a variety of strategies for fault tolerant encoding. For each specified algorithm, QuRE estimates quantities such as number of physical qubits, execution time, probability of success of the computation, and physical gate counts for elementary quantum gate types of a specified technology. Out of the box, QuRE supports estimation for six physical quantum technologies, seven quantum algorithms, and with error correction using the Steane [1], [2], Bacon-Shor [3], Knill [4] or surface [5], [6] error correction codes. Moreover, QuRE is extendable and can easily accommodate other choices. After describing QuRE, we use it to investigate the tradeoff between concatenated and surface error correction coding techniques, demonstrating the existence of a crossover point for the Ground State Estimation Algorithm [7].

We explore BGP safety, the question of whether a BGP system converges to a stable routing, in light of several BGP implementation features that have not been fully included in the previous theoretical analyses. We show that Route Flap Damping, MRAI timers, and other intra-router features can cause a router to briefly send “spurious” announcements of less-preferred routes. We demonstrate that, even in simple configurations, this short-term spurious behavior may cause long-term divergence in global routing. We then present DPVP, a general model that unifies these sources of spurious announcements in order to examine their impact on BGP safety. In this new, more robust model of BGP behavior, we derive a necessary and sufficient condition for safety, which furthermore admits an efficient algorithm for checking BGP safety in most practical circumstances - two complementary results that have been elusive in the past decade's worth of classical studies of BGP convergence in more simple models. We also consider the implications of spurious updates for well-known results on dispute wheels and safety under filtering.

Today's networks typically handle traffic engineering (e.g., tuning the routing-protocol parameters to optimize the flow of traffic) and failure recovery (e.g., pre-installed backup paths) independently. In this paper, we propose a unified way to balance load efficiently under a wide range of failure scenarios. Our architecture supports flexible splitting of traffic over multiple precomputed paths, with efficient path-level failure detection and automatic load balancing over the remaining paths. We propose two candidate solutions that differ in how the routers rebalance the load after a failure, leading to a trade-off between router complexity and load-balancing performance. We present and solve the optimization problems that compute the configuration state for each router. Our experiments with traffic measurements and topology data (including shared risks in the underlying transport network) from a large ISP identify a "sweet spot" that achieves near-optimal load balancing under a variety of failure scenarios, with a relatively small amount of state in the routers. We believe that our solution for joint traffic engineering and failure recovery will appeal to Internet Service Providers as well as the operators of data-center networks.

MaxNet TCP is a congestion control protocol that uses explicit multi-bit signalling from routers to achieve desirable properties such as high throughput and low latency. In this paper we present an implementation of an extended version of MaxNet. Our contributions are threefold. First, we extend the original algorithm to give both provable stability and rate fairness. Second, we introduce the MaxStart algorithm which allows new MaxNet connections to reach their fair rates quickly. Third, we provide a Linux kernel implementation of the protocol. With no overhead but 24-bit price signals, our implementation scales from 32 bit/s to 1 peta-bit/s with a 0.001% rate accuracy. We confirm the theoretically predicted properties by performing a range of experiments at speeds up to 1 Gbit/sec and delays up to 180 ms on the WAN-in-Lab facility.

In the Internet today, traffic management spans congestion control (at end hosts), routing protocols (on routers), and traffic engineering (by network operators). Historically, this division of functionality evolved organically. In this paper, we perform a top-down redesign of traffic management using recent innovations in optimization theory. First, we propose an objective function that captures the goals of end users and network operators. Using all known optimization decomposition techniques, we generate four distributed algorithms that divide traffic over multiple paths based on feedback from the network links. Combining the best features of the algorithms, we construct TRUMP: a traffic management protocol that is distributed, adaptive, robust, flexible and easy to manage. Further, TRUMP can operate based on implicit feedback about packet loss and delay. We show that using optimization decompositions as a foundation, simulations as a building block, and human intuition as a guide can be a principled approach to protocol design.

Despite the pressing need to secure routing, none of the existing secure variants of BGP has been widely deployed. Due to the size and decentralized nature of the Internet, it became clear that any viable secure routing protocol must offer benefits also in its early stages of deployment. In order to determine when the protocols are not adoptable, we quantify the benefits offered by a partial deployment of an Idealized Secure BGP which is able to detect malicious routes with perfect accuracy. We also quantify the benefits of an imperfect version of the protocol. Subsequently, we conclude that even the best protocols which simply detect and avoid bogus routes do not offer good security performance except in limited scenarios. We offer alternative designs, and hope that our insights will result in a new secure routing protocol that will be more attractive to early adopters.