The quantum approximate optimization algorithm/quantum alternating operator ansatz (QAOA) is a heuristic to find approximate solutions of combinatorial optimization problems. Most of the literature is limited to quadratic problems without constraints. However, many practically relevant optimization problems do have (hard) constraints that need to be fulfilled. In this article, we present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space given by these constraints. We generalize the “XY”-mixer designed to preserve the subspace of “one-hot” states to the general case of subspaces given by a number of computational basis states. We expose the underlying mathematical structure which reveals more of how mixers work and how one can minimize their cost in terms of the number of CX gates, particularly when Trotterization is taken into account. Our analysis also leads to valid Trotterizations for an “XY”-mixer with fewer CX gates than is known to date. In view of practical implementations, we also describe algorithms for efficient decomposition into basis gates. Several examples of more general cases are presented and analyzed.

The weighted MAX $$k$$k -CUT problem consists of finding ak-partition of a given weighted undirected graphG(V, E), such that the sum of the weights of the crossing edges is maximized. The problem is of particular interest as it has a multitude of practical applications. We present a formulation of the weighted MAX $$k$$k -CUT suitable for running the quantum approximate optimization algorithm (QAOA) on noisy intermediate scale quantum (NISQ) devices to get approximate solutions. The new formulation uses a binary encoding that requires only $$|V|\log _2k$$|V|log2k qubits. The contributions of this paper are as follows: (i) a novel decomposition of the phase-separation operator based on the binary encoding into basis gates is provided for the MAX $$k$$k -CUT problem for $$k>2$$k>2 . (ii) Numerical simulations on a suite of test cases comparing different encodings are performed. (iii) An analysis of the resources (number of qubits, CX gates) of the different encodings is presented. (iv) Formulations and simulations are extended to the case of weighted graphs. For smallkand with further improvements whenkis not a power of two, our algorithm is a possible candidate to show quantum advantage on NISQ devices.

We present a novel formalism to both understand and construct mixers that preserve a given subspace. The method connects and utilizes the stabilizer formalism that is used in error correcting codes. This can be useful in the setting when the quantum approximate optimization algorithm (QAOA), a popular meta-heuristic for solving combinatorial optimization problems, is applied in the setting where the constraints of the problem lead to a feasible subspace that is large but easy to specify. The proposed method gives a systematic way to construct mixers that are resource efficient in the number of controlled not gates and can be understood as a generalization of the well-known X and XY mixers and a relaxation of the Grover mixer: Given a basis of any subspace, a resource efficient mixer can be constructed that preserves the subspace. The numerical examples provided show a dramatic reduction of CX gates when compared to previous results. We call our approach logical X-Mixer or logical X QAOA (LX-QAOA), since it can be understood as dividing the subspace into code spaces of stabilizers S and consecutively applying logical rotational X gates associated with these code spaces. Overall, we hope that this new perspective can lead to further insight into the development of quantum algorithms.

Reservoir computing on quantum computers has recently emerged as a potential resource for time series prediction, owing to its inherent complex dynamics. To advance Quantum Reservoir Computing (QRC) research, we have developed the Python package QuantumReservoirPy, which facilitates QRC using quantum circuits as reservoirs. The package is designed to be easy to use, while staying completely customizable. The resulting interface, similar to that of reservoirpy (Trouvain et al., 2020), simplifies the development of quantum reservoirs, and provides logical methods of comparison between reservoir architectures.