The Quantum Alternating Operator Ansatz (QAOA) is a prominent variational quantum algorithm for solving combinatorial optimization problems. Its effectiveness depends on identifying input parameters that yield high-quality solutions. However, understanding the complexity of training QAOA remains an under-explored area. Previous results have given analytical performance guarantees for a small, fixed number of parameters. At the opposite end of the spectrum, barren plateaus are likely to emerge at Ω (n) parameters for n qubits. In this work, we study the difficulty of training in the intermediate regime, which is the focus of most current numerical studies and near-term hardware implementations. Through extensive numerical analysis of the quality and quantity of local minima, we argue that QAOA landscapes can exhibit a superpolynomial growth in the number of low-quality local minima even when the number of parameters scales logarithmically with n. This means that the common technique of gradient descent from randomly initialized parameters is doomed to fail beyond small n, and emphasizes the need for good initial guesses of the optimal parameters.

Estimating the state preparation fidelity of highly entangled states on noisy intermediate-scale quantum (NISQ) devices is important for benchmarking and application considerations. Unfortunately, exact fidelity measurements quickly become prohibitively expensive, as they scale exponentially as O (3 N for N -qubit states, using full state tomography with measurements in all Pauli bases combinations. However, Somma et al.established that the complexity could be drastically reduced when looking at fidelity lower bounds for states that exhibit symmetries, such as Dicke states and GHZ states. These bounds must still be tight enough for larger states to provide reasonable estimations on NISQ devices. For the first time and more than 15 years after the theoretical introduction, we report meaningful lower bounds for the state preparation fidelity of all Dicke states up to N =10 and all GHZ states up to N =20 on Quantinuum H1 ion-trap systems using efficient implementations of recently proposed scalable circuits for these states. Our achieved lower bounds match or exceed previously reported exact fidelities on superconducting systems for much smaller states. Furthermore, we provide evidence that for large Dicke states \(\left|\smash{D_{N/2}^{N}} \right\rangle\) , we may resort to a GHZ-based approximate state preparation to achieve better fidelity. This work provides a path forward to benchmarking entanglement as NISQ devices improve in size and quality.

Quantum volume is a full-stack benchmark for near-term quantum computers. It quantifies the largest size of a square circuit which can be executed on the target device with reasonable fidelity. Error mitigation is a set of techniques intended to remove the effects of noise present in the computation of noisy quantum computers when computing an expectation value of interest. Effective quantum volume is a proposed metric that applies error mitigation to the quantum volume protocol to evaluate the effectiveness not only of the target device but also of the error mitigation algorithm. Digital zero-noise extrapolation is an error mitigation technique that estimates the noiseless expectation value using circuit folding to amplify errors by known scale factors and then extrapolating computed expectation values to the zero-noise limit. Here we demonstrate that zero-noise extrapolation, with global and local unitary folding with fractional scale factors, in conjunction with dynamical decoupling, can increase the effective quantum volume over the vendor-measured quantum volume. Specifically, we measure the effective quantum volume of four IBM Quantum superconducting processor units, obtaining values that are larger than the vendor-measured quantum volume on each device. This is the first such increase reported.

Estimating the state preparation fidelity of highly entangled states on noisy intermediate-scale quantum (NISQ) devices is an important task for benchmarking and application considerations. Unfortunately, exact fidelity measurements quickly become prohibitively expensive, as they scale exponentially as O(3N) for N-qubit states, using full state tomography with measurements in all Pauli bases combinations. However, Somma et al. [20] established that the complexity could be drastically reduced when looking at fidelity lower bounds for states that exhibit symmetries, such as Dicke States and GHZ States. For larger states, these bounds still need to be tight enough to provide reasonable estimations on NISQ devices.

We study the status of fair sampling on Noisy Intermediate Scale Quantum (NISQ) devices, in particular the IBM Q family of backends. Using the recently introduced Grover Mixer-QAOA algorithm for discrete optimization, we generate fair sampling circuits to solve six problems of varying difficulty, each with several optimal solutions, which we then run on twenty backends across the IBM Q system. For a given circuit evaluated on a specific set of qubits, we evaluate: how frequently the qubits return an optimal solution to the problem, the fairness with which the qubits sample from all optimal solutions, and the reported hardware error rate of the qubits. To quantify fairness, we define a novel metric based on Pearson’s χ 2 test. We find that fairness is relatively high for circuits with small and large error rates, but drops for circuits with medium error rates. This indicates that structured errors dominate in this regime, while unstructured errors, which are random and thus inherently fair, dominate in noisier qubits and longer circuits. Our results show that fairness can be a powerful tool for understanding the intricate web of errors affecting current NISQ hardware.

As quantum computers become available to the general public, the need has arisen to train a cohort of quantum programmers, many of whom have been developing classical computer programs for most of their careers. While currently available quantum computers have less than 100 qubits, quantum computing hardware is widely expected to grow in terms of qubit count, quality, and connectivity. This review aims at explaining the principles of quantum programming, which are quite different from classical programming, with straightforward algebra that makes understanding of the underlying fascinating quantum mechanical principles optional. We give an introduction to quantum computing algorithms and their implementation on real quantum hardware. We survey 20 different quantum algorithms, attempting to describe each in a succinct and self-contained fashion. We show how these algorithms can be implemented on IBM’s quantum computer, and in each case, we discuss the results of the implementation with respect to differences between the simulator and the actual hardware runs. This article introduces computer scientists, physicists, and engineers to quantum algorithms and provides a blueprint for their implementations.

We consider the problem of collectively delivering some package from a specified source to a designated target location in a graph, using multiple mobile agents. Each agent has limited energy which constrains the distance it can move. Hence multiple agents need to collaborate to move the package, each agent handing over the package to the next agent to carry it forward. Given the positions of the agents in the graph and their respective budgets, the problem of finding a feasible movement schedule for the agents can be challenging. We consider two variants of the problem: in non-returning delivery, the agents can stop anywhere; whereas in returning delivery, each agent needs to return to its starting location, a variant which has not been studied before. We first provide a polynomial-time algorithm for returning delivery on trees, which is in contrast to the known (weak) NP-hardness of the non-returning version. In addition, we give resource-augmented algorithms for returning delivery in general graphs. Finally, we give tight lower bounds on the required resource augmentation for both variants of the problem. In this sense, our results close the gap left by previous research.

We consider k mobile agents initially located at distinct nodes of an undirected graph (on n nodes, with edge lengths) that have to deliver a single item from a given source node s to a given target node t. The agents can move along the edges of the graph, starting at time 0 with respect to the following: Each agent i has a weight w_i that defines the rate of energy consumption while travelling a distance in the graph, and a velocity v_i with which it can move. We are interested in schedules (operating the k agents) that result in a small delivery time T (time when the package arrives at t), and small total energy consumption E. Concretely, we ask for a schedule that: either (i) Minimizes T, (ii) Minimizes lexicographically (T,E) (prioritizing fast delivery), or (iii) Minimizes epsilon*T + (1-epsilon)*E, for a given epsilon, 0

We study the game-theoretic task of selecting mobile agents to deliver multiple items on a network. An instance is given by $m$ packages (physical objects) which have to be transported between specified source-target pairs in an undirected graph, and $k$ mobile heterogeneous agents, each being able to transport one package at a time. Following a recent model [Baertschi et al. 2017], each agent i has a different rate of energy consumption per unit distance traveled, i.e., its weight. We are interested in optimizing or approximating the total energy consumption over all selected agents. Unlike previous research, we assume the weights to be private values known only to the respective agents. We present three different mechanisms which select, route and pay the agents in a truthful way that guarantees voluntary participation of the agents, while approximating the optimum energy consumption by a constant factor. To this end, we analyze a previous structural result and an approximation algorithm given in [Baertschi et al. 2017]. Finally, we show that for some instances in the case of a single package, the sum of the payments can be bounded in terms of the optimum.

In chromatic variants of the art gallery problem, simple polygons are guarded with point guards that are assigned one of k colors each. We say these guards cover the polygon. Here we consider the conflict-free chromatic art gallery problem, first studied by Bärtschi and Suri (Algorithmica 2013): A covering of the polygon is conflict-free if each point of the polygon is seen by some guard whose color appears exactly once among the guards visible to that point. We are interested in the smallest number k(n) of colors that ensure such a covering for every n-vertex polygon.

We consider a chromatic variant of the art gallery problem, where each guard is assigned one of k distinct colors. A placement of such colored guards is conflict-free if each point of the polygon is seen by some guard whose color appears exactly once among the guards visible to that point. What is the smallest number k(n) of colors that ensure a conflict-free covering of all n-vertex polygons? We call this the conflict-free chromatic art gallery problem. The problem is motivated by applications in distributed robotics and wireless sensor networks where colors indicate the wireless frequencies assigned to a set of covering "landmarks" in the environment so that a mobile robot can always communicate with at least one landmark in its line-of-sight range without interference. Our main result shows that k(n) is O(log n) for orthogonal and for monotone polygons, and O(log^2 n) for arbitrary simple polygons. By contrast, if all guards visible from each point must have distinct colors, then k(n)is Omega(n) for arbitrary simple polygons and Omega(sqrt(n)) for orthogonal polygons, as shown by Erickson and LaValle [Proc. of RSS 2011].