3 September 2020 in Physical Review Applied
Airlines today are faced with a number of large-scale scheduling problems. One such problem is the tail-assignment problem, which is the task of assigning individual aircraft to a given set of flights, minimizing the overall cost. Each aircraft is identified by the registration number on its tail fin. In this paper, we simulate the quantum approximate optimization algorithm (QAOA) applied to instances of this problem derived from real-world data. The QAOA is a variational hybrid quantum-classical algorithm recently introduced and likely to run on near-term quantum devices. The instances are reduced to fit on quantum devices with 8, 15, and 25 qubits. The reduction procedure leaves only one feasible solution per instance, which allows us to map the tail-assignment problem onto the exact-cover problem. We find that repeated runs of the QAOA identify the feasible solution with close to unit probability for all instances. Furthermore, we observe patterns in the variational parameters such that an interpolation strategy can be employed, which significantly simplifies the classical optimization part of the QAOA. Finally, we empirically find a relation between the connectivity of the problem graph and the single-shot success probability of the algorithm.
3 September 2020 in Physical Review Applied
Present-day, noisy, small or intermediate-scale quantum processors—although far from fault tolerant—support the execution of heuristic quantum algorithms, which might enable a quantum advantage, for example, when applied to combinatorial optimization problems. On small-scale quantum processors, validations of such algorithms serve as important technology demonstrators. We implement the quantum approximate optimization algorithm on our hardware platform, consisting of two superconducting transmon qubits and one parametrically modulated coupler. We solve small instances of the NP (nondeterministic polynomial time)-complete exact-cover problem, with 96.6% success probability, by iterating the algorithm up to level two.
8 December 2021 in PRX Quantum
Near-term quantum computers are limited by the decoherence of qubits to only being able to run low-depth quantum circuits with acceptable fidelity. This severely restricts what quantum algorithms can be compiled and implemented on such devices. One way to overcome these limitations is to expand the available gate set from single- and two-qubit gates to multiqubit gates, which entangle three or more qubits in a single step. Here, we show that such multiqubit gates can be realized by the simultaneous application of multiple two-qubit gates to a group of qubits where at least one qubit is involved in two or more of the two-qubit gates. Multiqubit gates implemented in this way are as fast as, or sometimes even faster than, the constituent two-qubit gates. Furthermore, these multiqubit gates do not require any modification of the quantum processor, but are ready to be used in current quantum-computing platforms. We demonstrate this idea for two specific cases: simultaneous controlled- gates and simultaneous iswap gates. We show how the resulting multiqubit gates relate to other well-known multiqubit gates and demonstrate through numerical simulations that they would work well in available quantum hardware, reaching gate fidelities well above 99%. We also present schemes for using these simultaneous two-qubit gates to swiftly create large entangled states like Dicke and Greenberger-Horne-Zeilinger states.
14 August 2024 in Quantum
Virtual distillation has been proposed as an error mitigation protocol for estimating the expectation values of observables in quantum algorithms. It proceeds by creating a cyclic permutation of noisy copies of a quantum state using a sequence of controlled-swap gates. If the noise does not shift the dominant eigenvector of the density operator away from the ideal state, then the error in expectation-value estimation can be exponentially reduced with . In practice, subsequent error mitigation techniques are required to suppress the effect of noise in the cyclic permutation circuit itself, leading to increased experimental complexity. Here, we perform a careful analysis of the effect of uncorrelated, identical noise in the cyclic permutation circuit and find that the estimation of expectation value of observables are robust against dephasing noise. We support the analytical result with numerical simulations and find that of errors are reduced for , with physical dephasing error probabilities as high as . Our results imply that a broad class of quantum algorithms can be implemented with higher accuracy in the near-term with qubit platforms where non-dephasing errors are suppressed, such as superconducting bosonic qubits and Rydberg atoms.
10 November 2026 in Scientific Reports
The Quantum Approximate Optimization Algorithm (QAOA)–a prominent candidate for near-term quantum computing applications–is tailored to find approximate solutions to combinatorial optimization problems using shallow quantum circuits. In this work, we investigate implementations of QAOA based on cat qubits, where the logical states $$|0\rangle$$ and $$|1\rangle$$ are represented by coherent states of opposite amplitudes, $$|\alpha \rangle$$ and $$|-\alpha \rangle$$ . Within this encoding, the primary source of noise–photon loss–induces a bias toward Z -type errors. We focus specifically on an imlementation employing Kerr resonators. By numerically simulating the gate sequences required for QAOA on these nonlinear resonators, we analyze performance on Max-Cut problems and benchmark it against conventional qubits realized as ideal two-level systems subject to single-photon loss. Our findings indicate that the use of cat qubits leads to improved approximation ratios for random Max-Cut instances compared to standard qubit encodings.