Long-step path-following algorithm for quantum information theory: Some numerical aspects and applications

Leonid Faybusovich; Cunlu Zhou

doi:10.3934/naco.2021017

Article Contents

2022, Volume 12, Issue 2: 445-467. Doi: 10.3934/naco.2021017

This issue Previous Article $ V $-$ E $-invexity in $ E $-differentiable multiobjective programming Next Article

Long-step path-following algorithm for quantum information theory: Some numerical aspects and applications

Leonid Faybusovich and
Cunlu Zhou

Department of Mathematics, University of Notre Dame, Notre Dame, IN 46556, USA

Received: June 2020

Revised: April 2021

Early access: May 2021

Published: June 2022

Abstract / Introduction Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

We consider some important computational aspects of the long-step path-following algorithm developed in our previous work and show that a broad class of complicated optimization problems arising in quantum information theory can be solved using this approach. In particular, we consider one difficult optimization problem involving the quantum relative entropy in quantum key distribution and show that our method can solve problems of this type much faster in comparison with (very few) available options.

Keywords:

Mathematics Subject Classification: Primary: 90C22, 90C30, 90C51, 81-08; Secondary: 90C25, 90C90.

Citation:

Full Text(HTML)

Table 2. Numerical results for QKD optimization problem (68)

					Long-Step Path-Following			cvxquad $ + $ mosek
$ n $	$ k $	$ m $	$ r_1 $	$ r_2 $	$ T_{ac} $(s)	$ T_{pf} $(s)	$ nNewton $	$ f_{min} $	Time(s)	$ f_{min} $
4	8	2	2	2	0.15	0.03	6	0.2744	40.39	0.2744
6	12	4	1	2	0.15	0.15	14	0.0498	2751.39	0.0498
12	24	6	2	4	0.17	0.75	13	0.0440	N/A	failed
16	32	10	2	2	0.19	1.69	10	0.0511	N/A	failed
32	64	20	2	2	0.61	54.34	10	0.0332	N/A	failed

| Show Table

DownLoad: CSV

Table 1. Numerical Results for (63)

long-step path-following
$ n $	$ m $	$ N $	$ f_{min} $	$ nNewton $	$ T_{ac} $(s)	$ T_{pf} $(s)
4	2	4	27.3538	7	0.18	0.01
8	4	8	8.3264	13	0.19	0.03
16	8	16	18.4274	13	0.26	0.09
32	16	32	39.2516	21	1.39	1.06
64	32	64	91.6534	27	26.34	47.25

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	F. Alizadeh, J. Haeberly and M. Overton, Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results, SIAM Journal on Optimization, 8 (1998), 746-768. doi: 10.1137/S1052623496304700.
[2]	M. ApS, The MOSEK optimization toolbox for MATLAB manual, version 8.0 (revision 60), 2017, http://docs.mosek.com/8.0/toolbox/index.html.
[3]	C. Bachoc, D. C. Gijswijt, A. Schrijver and F. Vallentin, Invariant Semidefinite Programs, Springer US, Boston, MA, 2012. doi: 10.1007/978-1-4614-0769-0_9.
[4]	P. J. Coles, E. M. Metodiev and N. Ltkenhaus, Numerical approach for unstructured quantum key distribution, Nature Communications, 7 (2016), 11712.
[5]	B. Coutts, M. Girard and J. Watrous, Certifying optimality for convex quantum channel optimization problems, arXiv: 1810.13295, 2018.
[6]	D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, Springer, Netherlands, 1994. doi: 10.1007/978-94-011-1134-8.
[7]	D. den Hertog, C. Roos and T. Terlaky, On the classical logarithmic barrier function method for a class of smooth convex programming problems, J. Optim. Theory Appl., 73 (1992), 1-25. doi: 10.1007/BF00940075.
[8]	D. Drusvyatskiy and H. Wolkowicz, The Many Faces of Degeneracy in Conic Optimization, now, 2017.
[9]	H. Fawzi, J. Saunderson and P. A. Parrilo, Semidefinite approximations of the matrix logarithm, Found. Comput. Math., 19 (2019), 259-296. doi: 10.1007/s10208-018-9385-0.
[10]	H. Fawzi and O. Fawzi, Efficient optimization of the quantum relative entropy, J. Phys. A. Math. Theory, 51 (2018), 154003. doi: 10.1088/1751-8121/aab285.
[11]	L. Faybusovich and C. Zhou, Long-step path-following algorithm for solving symmetric programming problems with nonlinear objective functions, Comput. Optim. Appl., 72 (2019), 769-795. doi: 10.1007/s10589-018-0054-7.
[12]	L. Faybusovich and C. Zhou, Self-concordance and matrix monotonicity with applications to quantum entanglement problems, Applied Mathematics and Computation, 375 (2020), 125071. doi: 10.1016/j.amc.2020.125071.
[13]	K. Fujisawa, M. Kojima and K. Nakata, Exploiting sparsity in primal-dual interior-point methods for semidefinite programming, Mathematical Programming, 79 (1997), 235-253. doi: 10.1016/S0025-5610(97)00045-2.
[14]	R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, 1991. doi: 10.1017/CBO9780511840371.
[15]	H.-K. Lo, M. Curty and K. Tamaki, Secure quantum key distribution, Nat. Photon., 8 (2014), 595-604.
[16]	Y. Nesterov, Lectures on Convex Optimization, Springer International Publishing, 2018. doi: 10.1007/978-3-319-91578-4.
[17]	M. Pilanci and M. J. Wainwright, Newton sketch: A linear-time optimization algorithm with linear-quadratic convergence, 2015. doi: 10.1137/15M1021106.
[18]	V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dušek, N. Lütkenhaus and M. Peev, The security of practical quantum key distribution, Rev. Mod. Phys., 81 (2009), 1301-1350.
[19]	K. C. Toh, M. J. Todd and R. H. Tütüncü, SDPT3 –- a MATLAB software package for semidefinite programming, optimization methods and software, Optimization Methods and Software, 11 (1999), 545-581. doi: 10.1080/10556789908805762.
[20]	L. Vandenberghe and M. S. Andersen, Chordal Graphs and Semidefinite Optimization, Now Publishers, 2015.
[21]	A. Winick, N. Lütkenhaus and P. J. Coles, Reliable numerical key rates for quantum key distribution, Quantum, 2 (2018), 77.