We present a framework to deal with a range of large-scale compressive-sensing problems using a quantum subroutine. We apply a quantum approximate optimization algorithm (QAOA) to support detection in a sparse-signal reconstruction algorithm: matching pursuit. The constrained optimization required in this algorithm is difficult to handle when the size of the problem is large, and the constraints usually given by unstructured patterns also become an issue. Our framework utilizes specially designed structured constraints that are easy to manipulate and reduce the optimization problem to the solution of an Ising model which can be found using Ising solvers. In this study, we simulate QAOA for this purpose and evaluate the performances. We observe that our method can outperform reference classical methods in the same context. Our results explore a promising path for applying quantum computers in the compressive-sensing field.
We present a framework to deal with a range of large-scale compressive-sensing problems using a quantum subroutine. We apply a quantum approximate optimization algorithm (QAOA) to support detection in a sparse-signal reconstruction algorithm: matching pursuit. The constrained optimization required in this algorithm is difficult to handle when the size of the problem is large, and the constraints usually given by unstructured patterns also become an issue. Our framework utilizes specially designed structured constraints that are easy to manipulate and reduce the optimization problem to the solution of an Ising model which can be found using Ising solvers. In this study, we simulate QAOA for this purpose and evaluate the performances. We observe that our method can outperform reference classical methods in the same context. Our results explore a promising path for applying quantum computers in the compressive-sensing field.
Combinatorial optimization is a promising area for achieving quantum speedup. The quantum approximate optimization algorithm (QAOA) is designed to search for low-energy states of the Ising model, which correspond to near-optimal solutions of combinatorial optimization problems (COPs). However, effectively dealing with constraints of COPs remains a significant challenge. Existing methods, such as tailoring mixing operators, are typically limited to specific constraint types, like one-hot constraints. To address these limitations, we introduce a method for engineering a compressed space that represents the feasible solution space with fewer qubits than the original. Our approach includes a scalable technique for determining the unitary transformation between the compressed and original spaces on gate-based quantum computers. We then propose compressed space QAOA, which seeks near-optimal solutions within this reduced space, while utilizing the Ising model formulated in the original Hilbert space. Experimental results on a quantum simulator demonstrate the effectiveness of our method in solving various constrained COPs.
We employ spectral analysis and compressed sensing to identify settings where a variational algorithm's cost function can be recovered purely classically or with minimal quantum computer access. We present theoretical and numerical evidence supporting the viability of sparse recovery techniques. To demonstrate this approach, we use basis pursuit denoising to efficiently recover simulated Quantum Approximate Optimization Algorithm (QAOA) instances of large system size from very few samples. Our results indicate that sparse recovery can enable a more efficient use and distribution of quantum resources in the optimisation of variational algorithms.
Combinatorial optimization problems are at the heart of modern computational challenges; however, their NP-hard nature often makes exact classical solutions intractable. The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising candidate for NISQ-era optimization. However, a significant performance gap exists between unconstrained and constrained formulations. The former refers to problems in which each solution is valid, either bad or good. The latter, to tasks in which there exist illegal solutions. While native constrained QAOA mixers offer high solution quality, they often suffer from prohibitive runtimes. In this paper, we introduce LE-QAOA (L-reduction Enhanced QAOA), a framework that leverages classical complexity theory to bridge this gap. By utilizing L-reductions to map diverse problems into a canonical Max2SAT form, we are able to solve constrained problems using efficient unconstrained subroutines followed by a classical repairing tournament. Our results on the Maximum Independent Set (MIS) problem show that LE-QAOA achieves solution quality that matches and frequently exceeds that of native constrained solvers, while requiring as little as 10% of the execution time. This approach effectively combines the scalability of unconstrained quantum evolution with the precision of constrained optimization. Moreover, this approach makes it possible to solve combinatorial optimization by reduction to a single chosen problem whose QAOA encoding is optimized, rather than explicitly building specific Hamiltonians.
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm that offers the potential to handle combinatorial optimization problems. Introducing constraints in such combinatorial optimization problems poses a significant challenge in the extensions of QAOA to support relevant larger-scale problems. This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace. We show that this method can be used for encoding any general form of constraints. One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz. This procedure gives the flexibility to control the depth of the circuit at the cost of the accuracy of enforcing the constraint, thus having immediate application in the Noisy Intermediate Scale Quantum (NISQ) era. We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints. Finally, using this metric, we evaluate the performance of the proposed algorithm.
Compressive sensing is a novel approach that linearly samples sparse or compressible signals at a rate much below the Nyquist-Shannon sampling rate and outperforms traditional signal processing techniques in acquiring and reconstructing such signals. Compressive sensing with matrix uncertainty is an extension of the standard compressive sensing problem that appears in various applications including but not limited to cognitive radio sensing, calibration of the antenna, and deconvolution. The original problem of compressive sensing is NP-hard so the traditional techniques, such as convex and nonconvex relaxations and greedy algorithms, apply stringent constraints on the measurement matrix to indirectly handle this problem in the realm of classical computing. We propose well-posed approaches for both binary compressive sensing and binary compressive sensing with matrix uncertainty problems that are tractable by quantum annealers. Our approach formulates an Ising model whose ground state represents a sparse solution for the binary compressive sensing problem and then employs an alternating minimization scheme to tackle the binary compressive sensing with matrix uncertainty problem. This setting only requires the solution uniqueness of the considered problem to have a successful recovery process, and therefore the required conditions on the measurement matrix are notably looser. As a proof of concept, we can demonstrate the applicability of the proposed approach on the D-Wave quantum annealers; however, we can adapt our method to employ other modern computing phenomena -like adiabatic quantum computers (in general), CMOS annealers, optical parametric oscillators, and neuromorphic computing.
The integration of quantum algorithms into machine learning pipelines offers a promising direction for addressing complex combinatorial optimization problems inherent in graph-structured data. This study investigates the use of the Quantum Approximate Optimization Algorithm (QAOA) as a quantum subroutine within a hybrid quantum–classical framework to enhance machine learning solutions for graph-based tasks. QAOA is employed to solve NP-hard graph optimization problems such as Max-Cut, graph coloring, and community detection, which are reformulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. The solutions provided by QAOA are then incorporated into machine learning models, such as Graph Neural Networks (GNNs) or clustering algorithms, as enriched features or optimized graph partitions. The hybrid approach is evaluated on benchmark datasets, demonstrating competitive accuracy and improved scalability in certain problem instances compared to purely classical methods. The findings highlight the potential of leveraging near-term quantum hardware for augmenting classical learning systems in domains such as logistics, social network analysis, and computational biology.