Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Variational Quantum Optimization with Multi-Basis Encodings

Taylor L. Patti, Jean Kossaifi, Animashree Anandkumar, Susanne F. Yelin

Published Nov 12, 2021• 6 citations
Publisher

Abstract

Abstract Despite extensive research efforts, few quantum algorithms for classical optimization demonstrate realizable quantum advantage. The utility of many quantum algorithms is limited by high requisite circuit depth and nonconvex optimization landscapes. We tackle these challenges by introducing a new variational quantum algorithm that utilizes multi-basis graph encodings and nonlinear activation functions. Our technique results in increased optimization performance, a factor of two increase in effective quantum resources, and a quadratic reduction in measurement complexity. While the classical simulation of many qubits with traditional quantum formalism is impossible due to its exponential scaling, we mitigate this limitation with exact circuit representations using factorized tensor rings. In particular, the shallow circuits permitted by our technique, combined with efficient factorized tensor-based simulation, enable us to successfully optimize the MaxCut of the nonlocal 512-vertex DIMACS library graphs on a single GPU. By improving the performance of quantum optimization algorithms while requiring fewer quantum resources and utilizing shallower, more error-resistant circuits, we offer tangible progress for variational quantum optimization.

DOI
10.21203/rs.3.rs-654802/v2

Related papers

Variational Quantum Optimization with Multi-Basis Encodings

Taylor L. Patti, Jean Kossaifi, Animashree Anandkumar +1 more

Despite extensive research efforts, few quantum algorithms for classical optimization demonstrate realizable quantum advantage. The utility of many quantum algorithms is limited by high requisite circuit depth and nonconvex optimization landscapes. We tackle these challenges by introducing a new variational quantum algorithm that benefits from two innovations: multi-basis graph encodings and nonlinear activation functions. Our technique results in increased optimization performance, a factor of two increase in effective quantum resources, and a quadratic reduction in measurement complexity. While the classical simulation of many qubits with traditional quantum formalism is impossible due to its exponential scaling, we mitigate this limitation with exact circuit representations using factorized tensor rings. In particular, the shallow circuits permitted by our technique, combined with efficient factorized tensor-based simulation, enable us to successfully optimize the MaxCut of the nonlocally connected $512$-vertex DIMACS library graphs on a single GPU. By improving the performance of quantum optimization algorithms while requiring fewer quantum resources and utilizing shallower, more error-resistant circuits, we offer tangible progress for variational quantum optimization.

arXiv:2106.13304•Jun 24, 2021•0 citations

Variational quantum optimization with multibasis encodings

Taylor L. Patti, Jean Kossaifi, Animashree Anandkumar +1 more

Despite extensive research efforts, few quantum algorithms for classical optimization demonstrate a realizable quantum advantage. The utility of many quantum algorithms is limited by high requisite circuit depth and nonconvex optimization landscapes. We tackle these challenges by introducing a variational quantum algorithm that benefits from two innovations: multibasis graph encodings using single-qubit expectation values and nonlinear activation functions. Our technique results in increased observed optimization performance and a factor-of-two reduction in requisite qubits. While the classical simulation of many qubits with traditional quantum formalism is impossible due to its exponential scaling, we mitigate this limitation with exact circuit representations using factorized tensor rings. In particular, the shallow circuits permitted by our technique, combined with efficient factorized tensor-based simulation, enable us to successfully optimize the MaxCut of the 512-vertex DIMACS library graphs on a single GPU. By improving the performance of quantum optimization algorithms while requiring fewer quantum resources and utilizing shallower, more error-resistant circuits, we offer tangible progress for variational quantum optimization.

Physical Review Research•Aug 22, 2022•20 citations

Nonlinear Quantum Optimization Algorithms via Efficient Ising Model Encodings

Taylor L. Patti, Jean Kossaifi, Animashree Anandkumar +1 more

Abstract Despite extensive research efforts, few quantum algorithms for classical optimization demonstrate realizable advantage. The utility of many quantum algorithms is limited by high requisite circuit depth and nonconvex optimization landscapes. We tackle these challenges to quantum advantage with two new variational quantum algorithms, which utilize multi-basis graph encodings and nonlinear activation functions to outperform existing methods with remarkably shallow quantum circuits. Both algorithms provide a polynomial reduction in measurement complexity and either a factor of two speedup a factor of two reduction in quantum resources. Typically, the classical simulation of such algorithms with many qubits is impossible due to the exponential scaling of traditional quantum formalism and the limitations of tensor networks. Nonetheless, the shallow circuits and moderate entanglement of our algorithms, combined with efficient tensor method-based simulation, enable us to successfully optimize the MaxCut of high-connectivity global graphs with up to 512 nodes (qubits) on a single GPU.

•Jul 26, 2021•5 citations

Scalable Tensor Ring Methods for Variational Quantum Algorithms

Dheeraj Peddireddy

Variational quantum algorithms (VQAs) have emerged as a promising candidate for realizing quantum advantage in machine learning and optimization tasks on noisy intermediate-scale quantum (NISQ) devices. Despite significant theoretical promise, the practical impact of VQAs is constrained by the exponential growth in computational resources required for classical simulation, the onset of barren plateaus in parameterized landscapes, and the inherent difficulties of scaling classical optimization routines to circuits with many qubits and layers. Addressing these intertwined challenges is essential for both advancing quantum algorithm development and extracting actionable physical insights from modern quantum hardware.This dissertation develops, analyzes, and validates an efficient framework based on approximate tensor ring decompositions for the classical simulation, training, and benchmarking of variational quantum circuits and eigensolvers. The first component of this work formalizes the representation of quantum states and gates within a cyclic tensor ring structure, enabling the compression of parameterized quantum circuits to linear scaling in both qubit number and circuit depth, while preserving essential quantum correlations and entanglement structure. Gate operations are efficiently approximated via truncated singular value decomposition, and novel algorithms for forward propagation and gradient-based training in the tensor ring domain are developed. These methodological advances are systematically benchmarked on standard supervised learning tasks, including Iris and MNIST datasets, and compared to conventional statevector and matrix product state baselines, resulting in competitive accuracy and orders-of-magnitude reductions in simulation cost. Extending this framework, the dissertation also introduces a scalable method for gradient evaluation in variational quantum eigensolvers (VQE) using the approximate tensor ring representation. This approach enables the simulation and training of large circuits for combinatorial optimization problems, supporting practical qubit counts and circuit depths inaccessible to traditional simulation methods. Detailed experiments on the Maximum-Cut optimization problem demonstrate both the computational efficiency and robustness of the tensor ring framework in nontrivial optimization landscapes.Collectively, the results establish approximate tensor ring decomposition as a versatile and powerful framework for advancing quantum machine learning and discrete optimization, supporting both pre-deployment benchmarking on classical hardware and algorithm design for next-generation quantum devices. This work provides a foundation for the further exploration of scalable quantum-classical hybrid algorithms, with implications for quantum simulation, optimization, and beyond.

•Jan 20, 2026•0 citations

A Variational Qubit-Efficient MaxCut Heuristic Algorithm

Yovav Tene-Cohen, Tomer Kelman, Ohad Lev +1 more

Abstract MaxCut is a key NP-hard combinatorial optimization problem. Quantum computing offers methods to solve such problems potentially better than classical counterparts, with the Quantum Approximate Optimization Algorithm (QAOA) being a state-of-the-art example. However, the performance of quantum methods is currently hindered by hardware noise and limited qubit volumes. We present a variational Qubit-Efficient MaxCut (QEMC) algorithm that requires only $$O(\log N)$$ O ( log N ) qubits to tackle graphs of size N , an exponential reduction compared to QAOA. We demonstrate cutting-edge performance for 32-node graph instances (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) via classical simulations. The QEMC algorithm is based on an innovative encoding scheme, with potentially broad applicability, that empowers it with strong noise resilience, but also enables its efficient classical simulation. As such, the QEMC algorithm provides a challenging benchmark for QAOA on noisy devices and offers a novel quantum-inspired approach.

arXiv:2308.10383•npj Quantum Information•Feb 16, 2026•3 citations

Towards large-scale quantum optimization solvers with few qubits

Marco Sciorilli, Lucas Borges, Taylor L. Patti +4 more

Quantum computers hold the promise of more efficient combinatorial optimization solvers, which could be game-changing for a broad range of applications. However, a bottleneck for materializing such advantages is that, in order to challenge classical algorithms in practice, mainstream approaches require a number of qubits prohibitively large for near-term hardware. Here we introduce a variational solver for MaxCut problems over $$m={{\mathcal{O}}}({n}^{k})$$ binary variables using only n qubits, with tunable k > 1. The number of parameters and circuit depth display mild linear and sublinear scalings in m, respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. Altogether, this leads to high quantum-solver performances. For instance, for m = 7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m = 2000, experiments with n = 17 trapped-ion qubits feature MaxCut approximation ratios estimated to be beyond the hardness threshold 0.941. Our findings offer an interesting heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near-term quantum devices. Combinatorial optimization problems might be solvable more efficiently with quantum computing, but near-term quantum optimization solvers are limited in qubit size. Here, the authors propose and demonstrate a variational quantum algorithm that polynomially reduces the qubit overhead for applications like MaxCut.

arXiv:2401.09421•Nature Communications•Jan 8, 2025•47 citations
Abstract Despite extensive research efforts, few quantum algorithms for classical optimization demonstrate realizable quantum advantage. The utility of many quantum algorithms is limited by high requisite circuit depth and nonconvex optimization landscapes. We tackle these challenges by introducing a new variational quantum algorithm that utilizes multi-basis graph encodings and nonlinear activation functions. Our technique results in increased optimization performance, a factor of two increase in effective quantum resources, and a quadratic reduction in measurement complexity. While the classical simulation of many qubits with traditional quantum formalism is impossible due to its exponential scaling, we mitigate this limitation with exact circuit representations using factorized tensor rings. In particular, the shallow circuits permitted by our technique, combined with efficient factorized tensor-based simulation, enable us to successfully optimize the MaxCut of the nonlocal 512-vertex DIMACS library graphs on a single GPU. By improving the performance of quantum optimization algorithms while requiring fewer quantum resources and utilizing shallower, more error-resistant circuits, we offer tangible progress for variational quantum optimization.
Despite extensive research efforts, few quantum algorithms for classical optimization demonstrate realizable quantum advantage. The utility of many quantum algorithms is limited by high requisite circuit depth and nonconvex optimization landscapes. We tackle these challenges by introducing a new variational quantum algorithm that benefits from two innovations: multi-basis graph encodings and nonlinear activation functions. Our technique results in increased optimization performance, a factor of two increase in effective quantum resources, and a quadratic reduction in measurement complexity. While the classical simulation of many qubits with traditional quantum formalism is impossible due to its exponential scaling, we mitigate this limitation with exact circuit representations using factorized tensor rings. In particular, the shallow circuits permitted by our technique, combined with efficient factorized tensor-based simulation, enable us to successfully optimize the MaxCut of the nonlocally connected 512512512-vertex DIMACS library graphs on a single GPU. By improving the performance of quantum optimization algorithms while requiring fewer quantum resources and utilizing shallower, more error-resistant circuits, we offer tangible progress for variational quantum optimization.
Despite extensive research efforts, few quantum algorithms for classical optimization demonstrate a realizable quantum advantage. The utility of many quantum algorithms is limited by high requisite circuit depth and nonconvex optimization landscapes. We tackle these challenges by introducing a variational quantum algorithm that benefits from two innovations: multibasis graph encodings using single-qubit expectation values and nonlinear activation functions. Our technique results in increased observed optimization performance and a factor-of-two reduction in requisite qubits. While the classical simulation of many qubits with traditional quantum formalism is impossible due to its exponential scaling, we mitigate this limitation with exact circuit representations using factorized tensor rings. In particular, the shallow circuits permitted by our technique, combined with efficient factorized tensor-based simulation, enable us to successfully optimize the MaxCut of the 512-vertex DIMACS library graphs on a single GPU. By improving the performance of quantum optimization algorithms while requiring fewer quantum resources and utilizing shallower, more error-resistant circuits, we offer tangible progress for variational quantum optimization.
Abstract Despite extensive research efforts, few quantum algorithms for classical optimization demonstrate realizable advantage. The utility of many quantum algorithms is limited by high requisite circuit depth and nonconvex optimization landscapes. We tackle these challenges to quantum advantage with two new variational quantum algorithms, which utilize multi-basis graph encodings and nonlinear activation functions to outperform existing methods with remarkably shallow quantum circuits. Both algorithms provide a polynomial reduction in measurement complexity and either a factor of two speedup a factor of two reduction in quantum resources. Typically, the classical simulation of such algorithms with many qubits is impossible due to the exponential scaling of traditional quantum formalism and the limitations of tensor networks. Nonetheless, the shallow circuits and moderate entanglement of our algorithms, combined with efficient tensor method-based simulation, enable us to successfully optimize the MaxCut of high-connectivity global graphs with up to 512 nodes (qubits) on a single GPU.
Variational quantum algorithms (VQAs) have emerged as a promising candidate for realizing quantum advantage in machine learning and optimization tasks on noisy intermediate-scale quantum (NISQ) devices. Despite significant theoretical promise, the practical impact of VQAs is constrained by the exponential growth in computational resources required for classical simulation, the onset of barren plateaus in parameterized landscapes, and the inherent difficulties of scaling classical optimization routines to circuits with many qubits and layers. Addressing these intertwined challenges is essential for both advancing quantum algorithm development and extracting actionable physical insights from modern quantum hardware.This dissertation develops, analyzes, and validates an efficient framework based on approximate tensor ring decompositions for the classical simulation, training, and benchmarking of variational quantum circuits and eigensolvers. The first component of this work formalizes the representation of quantum states and gates within a cyclic tensor ring structure, enabling the compression of parameterized quantum circuits to linear scaling in both qubit number and circuit depth, while preserving essential quantum correlations and entanglement structure. Gate operations are efficiently approximated via truncated singular value decomposition, and novel algorithms for forward propagation and gradient-based training in the tensor ring domain are developed. These methodological advances are systematically benchmarked on standard supervised learning tasks, including Iris and MNIST datasets, and compared to conventional statevector and matrix product state baselines, resulting in competitive accuracy and orders-of-magnitude reductions in simulation cost. Extending this framework, the dissertation also introduces a scalable method for gradient evaluation in variational quantum eigensolvers (VQE) using the approximate tensor ring representation. This approach enables the simulation and training of large circuits for combinatorial optimization problems, supporting practical qubit counts and circuit depths inaccessible to traditional simulation methods. Detailed experiments on the Maximum-Cut optimization problem demonstrate both the computational efficiency and robustness of the tensor ring framework in nontrivial optimization landscapes.Collectively, the results establish approximate tensor ring decomposition as a versatile and powerful framework for advancing quantum machine learning and discrete optimization, supporting both pre-deployment benchmarking on classical hardware and algorithm design for next-generation quantum devices. This work provides a foundation for the further exploration of scalable quantum-classical hybrid algorithms, with implications for quantum simulation, optimization, and beyond.
Abstract MaxCut is a key NP-hard combinatorial optimization problem. Quantum computing offers methods to solve such problems potentially better than classical counterparts, with the Quantum Approximate Optimization Algorithm (QAOA) being a state-of-the-art example. However, the performance of quantum methods is currently hindered by hardware noise and limited qubit volumes. We present a variational Qubit-Efficient MaxCut (QEMC) algorithm that requires only O(log⁡N)O(\log N)O(logN) O ( log N ) qubits to tackle graphs of size N , an exponential reduction compared to QAOA. We demonstrate cutting-edge performance for 32-node graph instances (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) via classical simulations. The QEMC algorithm is based on an innovative encoding scheme, with potentially broad applicability, that empowers it with strong noise resilience, but also enables its efficient classical simulation. As such, the QEMC algorithm provides a challenging benchmark for QAOA on noisy devices and offers a novel quantum-inspired approach.
Quantum computers hold the promise of more efficient combinatorial optimization solvers, which could be game-changing for a broad range of applications. However, a bottleneck for materializing such advantages is that, in order to challenge classical algorithms in practice, mainstream approaches require a number of qubits prohibitively large for near-term hardware. Here we introduce a variational solver for MaxCut problems over m=O(nk)m={{\mathcal{O}}}({n}^{k})m=O(nk) binary variables using only n qubits, with tunable k > 1. The number of parameters and circuit depth display mild linear and sublinear scalings in m, respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. Altogether, this leads to high quantum-solver performances. For instance, for m = 7000, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for m = 2000, experiments with n = 17 trapped-ion qubits feature MaxCut approximation ratios estimated to be beyond the hardness threshold 0.941. Our findings offer an interesting heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near-term quantum devices. Combinatorial optimization problems might be solvable more efficiently with quantum computing, but near-term quantum optimization solvers are limited in qubit size. Here, the authors propose and demonstrate a variational quantum algorithm that polynomially reduces the qubit overhead for applications like MaxCut.