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

IET Quantum Communication

Majorisation‐minimisation algorithm for optimal state discrimination in quantum communications

Neel Kanth Kundu, Prabhu Babu, Petre Stoica

Published Aug 20, 2024• 2 citations
Publisher

Abstract

Abstract Designing optimal measurement operators for quantum state discrimination (QSD) is an important problem in quantum communications and cryptography applications. Prior works have demonstrated that optimal quantum measurement operators can be obtained by solving a convex semidefinite program (SDP). However, solving the SDP can represent a high computational burden for many real‐time quantum communication systems. To address this issue, a majorisation‐minimisation (MM)‐based algorithm, called Quantum Majorisation‐Minimisation (QMM) is proposed for solving the QSD problem. In QMM, the authors reparametrise the original objective, then tightly upper‐bound it at any given iterate, and obtain the next iterate as a closed‐form solution to the upper‐bound minimisation problem. Our numerical simulations demonstrate that the proposed QMM algorithm significantly outperforms the state‐of‐the‐art SDP algorithm in terms of speed, while maintaining comparable performance for solving QSD problems in quantum communication applications.

DOI
10.1049/qtc2.12107

Related papers

Minimum-error quantum state discrimination based on semidefinite programming

Wang Wengang, Guohua Dong, Mingshan Li

In this paper we consider the general problem of designing the optimal quantum detection for minimum-error quantum state discrimination. Since it is hard to get an explicit solution and we must resort to numerical methods for the general case. We show the problem can be cast into a semidefinite programming(SDP) problem, we use the theory of SDP to solve it. Based on the idea, we propose a method for minimum-error discrimination by formulating the design of optimal quantum detection as a standard SDP problem; furthermore, based on the optimality conditions for SDP, we derive a set of optimality conditions for quantum detection. It is exemplified that this method is simple to implement and can be used to design optimum detection operators for minimum-error discrimination efficiently.

Chinese Control Conference (CCC)•Jul 1, 2008•2 citations

Noisy intermediate-scale quantum algorithm for semidefinite programming

Kishor Bharti, Tobias Haug, Vlatko Vedral +1 more

Semidefinite programs (SDPs) are convex optimization programs with vast applications in control theory, quantum information, combinatorial optimization, and operational research. Noisy intermediate-scale quantum (NISQ) algorithms aim to make an efficient use of the current generation of quantum hardware. However, optimizing variational quantum algorithms is a challenge as it is an nondeterministic polynomial time-hard problem that in general requires an exponential time to solve and can contain many far from optimal local minima. Here, we present a current term NISQ algorithm for solving SDPs. The classical optimization program of our NISQ solver is another SDP over a lower dimensional ansatz space. We harness the SDP-based formulation of the Hamiltonian ground-state problem to design a NISQ eigensolver. Unlike variational quantum eigensolvers, the classical optimization program of our eigensolver is convex and can be solved in polynomial time with the number of ansatz parameters, and every local minimum is a global minimum. We find numeric evidence that NISQ SDP can improve the estimation of ground-state energies in a scalable manner. Further, we efficiently solve constrained problems to calculate the excited states of Hamiltonians, find the lowest energy of symmetry constrained Hamiltonians, and determine the optimal measurements for quantum state discrimination. We demonstrate the potential of our approach by finding the largest eigenvalue of up to ${2}^{1000}$ dimensional matrices and solving graph problems related to quantum contextuality. We also discuss NISQ algorithms for rank-constrained SDPs. Our work extends the application of NISQ computers onto one of the most successful algorithmic frameworks of the past few decades.

arXiv:2106.03891•Physical Review A•May 31, 2022•31 citations

Error-Tolerant Quantum State Discrimination: Optimization and Quantum Circuit Synthesis

Chien-Kai Ma, Bo-Hung Chen, Tian-Fu Chen +2 more

We develop error-tolerant quantum state discrimination(QSD) strategies that maintain reliable performance under moderate noise. Two complementary approaches are proposed: CrossQSD, which generalizes unambiguous discrimination with tunable confidence bounds to balance accuracy and efficiency, and FitQSD, which optimizes the measurement outcome distribution to approximate that of the ideal noiseless case. Furthermore, we provide a unified hybrid-objective QSD framework that continuously interpolates between minimum-error discrimination (MED) and FitQSD, allowing flexible trade-offs among competing objectives. The associated optimization problems are formulated as convex programs and efficiently solved via disciplined convex programming or, in many cases, semidefinite programming. Additionally, a circuit synthesis framework based on a modified Naimark dilation and isometry synthesis enables hardware-efficient implementations with substantially reduced qubit and gate resources. An open-source toolkit automates the full optimization and synthesis workflow, providing a practical route to QSD on current quantum devices.

quant-pharXiv:2602.10731•Lecture notes in computer science•Feb 12, 2026•0 citations

Quantum Alternating Direction Method of Multipliers for Semidefinite Programming

Hantao Nie, Dong Un An, Zaiwen Wen

Semidefinite programming (SDP) is a fundamental convex optimization problem with wide-ranging applications. However, solving large-scale instances remains computationally challenging due to the high cost of solving linear systems and performing eigenvalue decompositions. In this paper, we present a quantum alternating direction method of multipliers (QADMM) for SDPs, building on recent advances in quantum computing. An inexact ADMM framework is developed, which tolerates errors in the iterates arising from block-encoding approximation and quantum measurement. Within this robust scheme, we design a polynomial proximal operator to address the semidefinite conic constraints and apply the quantum singular value transformation to accelerate the most costly projection updates. We prove that the scheme converges to an ϵ -optimal solution of the SDP problem under the strong duality assumption. A detailed complexity analysis shows that the QADMM algorithm achieves favorable scaling with respect to dimension compared to the classical ADMM algorithm and quantum interior point methods, highlighting its potential for solving large-scale SDPs.

arXiv:2510.10056•Quantum•Jul 8, 2026•0 citations

Variational Quantum Algorithms for Semidefinite Programming

Dhrumil Patel, Patrick J. Coles, Mark M. Wilde

A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N ≫ M , where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.

arXiv:2112.08859•Quantum•Jun 17, 2024•16 citations

Designing optimal quantum detectors via semidefinite programming

Yonina C. Eldar, Alexandre Megretski, George C. Verghese

We consider the problem of designing an optimal quantum detector to minimize the probability of a detection error when distinguishing among a collection of quantum states, represented by a set of density operators. We show that the design of the optimal detector can be formulated as a semidefinite programming problem. Based on this formulation, we derive a set of necessary and sufficient conditions for an optimal quantum measurement. We then show that the optimal measurement can be found by solving a standard (convex) semidefinite program. By exploiting the many well-known algorithms for solving semidefinite programs, which are guaranteed to converge to the global optimum, the optimal measurement can be computed very efficiently in polynomial time within any desired accuracy. Using the semidefinite programming formulation, we also show that the rank of each optimal measurement operator is no larger than the rank of the corresponding density operator. In particular, if the quantum state ensemble is a pure-state ensemble consisting of (not necessarily independent) rank-one density operators, then we show that the optimal measurement is a pure-state measurement consisting of rank-one measurement operators.

arXiv:quant-ph/0205178•IEEE Transactions on Information Theory•Apr 1, 2003•168 citations
Abstract Designing optimal measurement operators for quantum state discrimination (QSD) is an important problem in quantum communications and cryptography applications. Prior works have demonstrated that optimal quantum measurement operators can be obtained by solving a convex semidefinite program (SDP). However, solving the SDP can represent a high computational burden for many real‐time quantum communication systems. To address this issue, a majorisation‐minimisation (MM)‐based algorithm, called Quantum Majorisation‐Minimisation (QMM) is proposed for solving the QSD problem. In QMM, the authors reparametrise the original objective, then tightly upper‐bound it at any given iterate, and obtain the next iterate as a closed‐form solution to the upper‐bound minimisation problem. Our numerical simulations demonstrate that the proposed QMM algorithm significantly outperforms the state‐of‐the‐art SDP algorithm in terms of speed, while maintaining comparable performance for solving QSD problems in quantum communication applications.
In this paper we consider the general problem of designing the optimal quantum detection for minimum-error quantum state discrimination. Since it is hard to get an explicit solution and we must resort to numerical methods for the general case. We show the problem can be cast into a semidefinite programming(SDP) problem, we use the theory of SDP to solve it. Based on the idea, we propose a method for minimum-error discrimination by formulating the design of optimal quantum detection as a standard SDP problem; furthermore, based on the optimality conditions for SDP, we derive a set of optimality conditions for quantum detection. It is exemplified that this method is simple to implement and can be used to design optimum detection operators for minimum-error discrimination efficiently.
Semidefinite programs (SDPs) are convex optimization programs with vast applications in control theory, quantum information, combinatorial optimization, and operational research. Noisy intermediate-scale quantum (NISQ) algorithms aim to make an efficient use of the current generation of quantum hardware. However, optimizing variational quantum algorithms is a challenge as it is an nondeterministic polynomial time-hard problem that in general requires an exponential time to solve and can contain many far from optimal local minima. Here, we present a current term NISQ algorithm for solving SDPs. The classical optimization program of our NISQ solver is another SDP over a lower dimensional ansatz space. We harness the SDP-based formulation of the Hamiltonian ground-state problem to design a NISQ eigensolver. Unlike variational quantum eigensolvers, the classical optimization program of our eigensolver is convex and can be solved in polynomial time with the number of ansatz parameters, and every local minimum is a global minimum. We find numeric evidence that NISQ SDP can improve the estimation of ground-state energies in a scalable manner. Further, we efficiently solve constrained problems to calculate the excited states of Hamiltonians, find the lowest energy of symmetry constrained Hamiltonians, and determine the optimal measurements for quantum state discrimination. We demonstrate the potential of our approach by finding the largest eigenvalue of up to 21000{2}^{1000}21000 dimensional matrices and solving graph problems related to quantum contextuality. We also discuss NISQ algorithms for rank-constrained SDPs. Our work extends the application of NISQ computers onto one of the most successful algorithmic frameworks of the past few decades.
We develop error-tolerant quantum state discrimination(QSD) strategies that maintain reliable performance under moderate noise. Two complementary approaches are proposed: CrossQSD, which generalizes unambiguous discrimination with tunable confidence bounds to balance accuracy and efficiency, and FitQSD, which optimizes the measurement outcome distribution to approximate that of the ideal noiseless case. Furthermore, we provide a unified hybrid-objective QSD framework that continuously interpolates between minimum-error discrimination (MED) and FitQSD, allowing flexible trade-offs among competing objectives. The associated optimization problems are formulated as convex programs and efficiently solved via disciplined convex programming or, in many cases, semidefinite programming. Additionally, a circuit synthesis framework based on a modified Naimark dilation and isometry synthesis enables hardware-efficient implementations with substantially reduced qubit and gate resources. An open-source toolkit automates the full optimization and synthesis workflow, providing a practical route to QSD on current quantum devices.
Semidefinite programming (SDP) is a fundamental convex optimization problem with wide-ranging applications. However, solving large-scale instances remains computationally challenging due to the high cost of solving linear systems and performing eigenvalue decompositions. In this paper, we present a quantum alternating direction method of multipliers (QADMM) for SDPs, building on recent advances in quantum computing. An inexact ADMM framework is developed, which tolerates errors in the iterates arising from block-encoding approximation and quantum measurement. Within this robust scheme, we design a polynomial proximal operator to address the semidefinite conic constraints and apply the quantum singular value transformation to accelerate the most costly projection updates. We prove that the scheme converges to an ϵ -optimal solution of the SDP problem under the strong duality assumption. A detailed complexity analysis shows that the QADMM algorithm achieves favorable scaling with respect to dimension compared to the classical ADMM algorithm and quantum interior point methods, highlighting its potential for solving large-scale SDPs.
A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N ≫ M , where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.
We consider the problem of designing an optimal quantum detector to minimize the probability of a detection error when distinguishing among a collection of quantum states, represented by a set of density operators. We show that the design of the optimal detector can be formulated as a semidefinite programming problem. Based on this formulation, we derive a set of necessary and sufficient conditions for an optimal quantum measurement. We then show that the optimal measurement can be found by solving a standard (convex) semidefinite program. By exploiting the many well-known algorithms for solving semidefinite programs, which are guaranteed to converge to the global optimum, the optimal measurement can be computed very efficiently in polynomial time within any desired accuracy. Using the semidefinite programming formulation, we also show that the rank of each optimal measurement operator is no larger than the rank of the corresponding density operator. In particular, if the quantum state ensemble is a pure-state ensemble consisting of (not necessarily independent) rank-one density operators, then we show that the optimal measurement is a pure-state measurement consisting of rank-one measurement operators.