American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Smooth augmented Lagrangian method for twin bounded support vector machine
  • NACO Home
  • This Issue
  • Next Article
    A novel methodology for portfolio selection in fuzzy multi criteria environment using risk-benefit analysis and fractional stochastic
doi: 10.3934/naco.2021017
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

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: long-step path-following algorithm, self-concordant functions, matrix monotone functions, quantum relative entropy, quantum key distribution, quantum information theory.
Mathematics Subject Classification: Primary: 90C22, 90C30, 90C51, 81-08; Secondary: 90C25, 90C90.
Citation: Leonid Faybusovich, Cunlu Zhou. Long-step path-following algorithm for quantum information theory: Some numerical aspects and applications. Numerical Algebra, Control & Optimization, doi: 10.3934/naco.2021017
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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[4]

P. J. Coles, E. M. Metodiev and N. Ltkenhaus, Numerical approach for unstructured quantum key distribution, Nature Communications, 7 (2016), 11712.  Google Scholar

[5]

B. Coutts, M. Girard and J. Watrous, Certifying optimality for convex quantum channel optimization problems, arXiv: 1810.13295, 2018. Google Scholar

[6]

D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, Springer, Netherlands, 1994. doi: 10.1007/978-94-011-1134-8.  Google Scholar

[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.  Google Scholar

[8]

D. Drusvyatskiy and H. Wolkowicz, The Many Faces of Degeneracy in Conic Optimization, now, 2017. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14] R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, 1991.  doi: 10.1017/CBO9780511840371.  Google Scholar
[15]

H.-K. Lo, M. Curty and K. Tamaki, Secure quantum key distribution, Nat. Photon., 8 (2014), 595-604.   Google Scholar

[16]

Y. Nesterov, Lectures on Convex Optimization, Springer International Publishing, 2018. doi: 10.1007/978-3-319-91578-4.  Google Scholar

[17]

M. Pilanci and M. J. Wainwright, Newton sketch: A linear-time optimization algorithm with linear-quadratic convergence, 2015. doi: 10.1137/15M1021106.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[20]

L. Vandenberghe and M. S. Andersen, Chordal Graphs and Semidefinite Optimization, Now Publishers, 2015. Google Scholar

[21]

A. Winick, N. Lütkenhaus and P. J. Coles, Reliable numerical key rates for quantum key distribution, Quantum, 2 (2018), 77. Google Scholar

show all references

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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[4]

P. J. Coles, E. M. Metodiev and N. Ltkenhaus, Numerical approach for unstructured quantum key distribution, Nature Communications, 7 (2016), 11712.  Google Scholar

[5]

B. Coutts, M. Girard and J. Watrous, Certifying optimality for convex quantum channel optimization problems, arXiv: 1810.13295, 2018. Google Scholar

[6]

D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, Springer, Netherlands, 1994. doi: 10.1007/978-94-011-1134-8.  Google Scholar

[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.  Google Scholar

[8]

D. Drusvyatskiy and H. Wolkowicz, The Many Faces of Degeneracy in Conic Optimization, now, 2017. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14] R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge University Press, 1991.  doi: 10.1017/CBO9780511840371.  Google Scholar
[15]

H.-K. Lo, M. Curty and K. Tamaki, Secure quantum key distribution, Nat. Photon., 8 (2014), 595-604.   Google Scholar

[16]

Y. Nesterov, Lectures on Convex Optimization, Springer International Publishing, 2018. doi: 10.1007/978-3-319-91578-4.  Google Scholar

[17]

M. Pilanci and M. J. Wainwright, Newton sketch: A linear-time optimization algorithm with linear-quadratic convergence, 2015. doi: 10.1137/15M1021106.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[20]

L. Vandenberghe and M. S. Andersen, Chordal Graphs and Semidefinite Optimization, Now Publishers, 2015. Google Scholar

[21]

A. Winick, N. Lütkenhaus and P. J. Coles, Reliable numerical key rates for quantum key distribution, Quantum, 2 (2018), 77. Google Scholar

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
Table Options

Download as excel

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
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
Table Options

Download as excel

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
[1]

Luiza H. F. Andrade, Rui F. Vigelis, Charles C. Cavalcante. A generalized quantum relative entropy. Advances in Mathematics of Communications, 2020, 14 (3) : 413-422. doi: 10.3934/amc.2020063
[2]

Huai-Dong Cao and Jian Zhou. On quantum de Rham cohomology theory. Electronic Research Announcements, 1999, 5: 24-34.

[3]

Mathieu Molitor. On the relation between geometrical quantum mechanics and information geometry. Journal of Geometric Mechanics, 2015, 7 (2) : 169-202. doi: 10.3934/jgm.2015.7.169
[4]

Helmut Kröger. From quantum action to quantum chaos. Conference Publications, 2003, 2003 (Special) : 492-500. doi: 10.3934/proc.2003.2003.492
[5]

Alberto Ibort, Alberto López-Yela. Quantum tomography and the quantum Radon transform. Inverse Problems & Imaging, 2021, 15 (5) : 893-928. doi: 10.3934/ipi.2021021
[6]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451
[7]

Liming Sun, Li-Zhi Liao. An interior point continuous path-following trajectory for linear programming. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1517-1534. doi: 10.3934/jimo.2018107
[8]

Sang-Gyun Youn. On the Sobolev embedding properties for compact matrix quantum groups of Kac type. Communications on Pure & Applied Analysis, 2020, 19 (6) : 3341-3366. doi: 10.3934/cpaa.2020148
[9]

Giuseppe Marmo, Giuseppe Morandi, Narasimhaiengar Mukunda. The Hamilton-Jacobi theory and the analogy between classical and quantum mechanics. Journal of Geometric Mechanics, 2009, 1 (3) : 317-355. doi: 10.3934/jgm.2009.1.317
[10]

Weinan E, Jianfeng Lu. Mathematical theory of solids: From quantum mechanics to continuum models. Discrete & Continuous Dynamical Systems, 2014, 34 (12) : 5085-5097. doi: 10.3934/dcds.2014.34.5085
[11]

Paolo Antonelli, Pierangelo Marcati. Quantum hydrodynamics with nonlinear interactions. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 1-13. doi: 10.3934/dcdss.2016.9.1
[12]

Gabriel Rivière. Remarks on quantum ergodicity. Journal of Modern Dynamics, 2013, 7 (1) : 119-133. doi: 10.3934/jmd.2013.7.119
[13]

Sergei Avdonin, Pavel Kurasov. Inverse problems for quantum trees. Inverse Problems & Imaging, 2008, 2 (1) : 1-21. doi: 10.3934/ipi.2008.2.1
[14]

Dmitry Jakobson. On quantum limits on flat tori. Electronic Research Announcements, 1995, 1: 80-86.

[15]

James B. Kennedy, Jonathan Rohleder. On the hot spots of quantum graphs. Communications on Pure & Applied Analysis, 2021, 20 (9) : 3029-3063. doi: 10.3934/cpaa.2021095
[16]

Jin-Cheng Jiang, Chi-Kun Lin, Shuanglin Shao. On one dimensional quantum Zakharov system. Discrete & Continuous Dynamical Systems, 2016, 36 (10) : 5445-5475. doi: 10.3934/dcds.2016040
[17]

Dubi Kelmer. Quantum ergodicity for products of hyperbolic planes. Journal of Modern Dynamics, 2008, 2 (2) : 287-313. doi: 10.3934/jmd.2008.2.287
[18]

Ruikuan Liu, Tian Ma, Shouhong Wang, Jiayan Yang. Thermodynamical potentials of classical and quantum systems. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1411-1448. doi: 10.3934/dcdsb.2018214
[19]

Mason A. Porter, Richard L. Liboff. The radially vibrating spherical quantum billiard. Conference Publications, 2001, 2001 (Special) : 310-318. doi: 10.3934/proc.2001.2001.310
[20]

Jianhong (Jackie) Shen, Sung Ha Kang. Quantum TV and applications in image processing. Inverse Problems & Imaging, 2007, 1 (3) : 557-575. doi: 10.3934/ipi.2007.1.557

 Impact Factor: 

Tools

Metrics

  • PDF downloads (87)
  • HTML views (221)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences