- Previous Article
- NACO Home
- This Issue
-
Next Article
$ V $-$ E $-invexity in $ E $-differentiable multiobjective programming
Long-step path-following algorithm for quantum information theory: Some numerical aspects and applications
Department of Mathematics, University of Notre Dame, Notre Dame, IN 46556, USA |
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.
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. |
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. |
[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. |
Long-Step Path-Following | cvxquad |
|||||||||
Time(s) | ||||||||||
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 |
Long-Step Path-Following | cvxquad |
|||||||||
Time(s) | ||||||||||
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 |
long-step path-following | ||||||
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 |
long-step path-following | ||||||
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] |
Suman Dutta, Subhamoy Maitra, Chandra Sekhar Mukherjee. Following Forrelation – quantum algorithms in exploring Boolean functions' spectra. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2021067 |
[3] |
Huai-Dong Cao and Jian Zhou. On quantum de Rham cohomology theory. Electronic Research Announcements, 1999, 5: 24-34. |
[4] |
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 |
[5] |
Helmut Kröger. From quantum action to quantum chaos. Conference Publications, 2003, 2003 (Special) : 492-500. doi: 10.3934/proc.2003.2003.492 |
[6] |
Alberto Ibort, Alberto López-Yela. Quantum tomography and the quantum Radon transform. Inverse Problems and Imaging, 2021, 15 (5) : 893-928. doi: 10.3934/ipi.2021021 |
[7] |
Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete and Continuous Dynamical Systems - S, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451 |
[8] |
Liming Sun, Li-Zhi Liao. An interior point continuous path-following trajectory for linear programming. Journal of Industrial and Management Optimization, 2019, 15 (4) : 1517-1534. doi: 10.3934/jimo.2018107 |
[9] |
Sang-Gyun Youn. On the Sobolev embedding properties for compact matrix quantum groups of Kac type. Communications on Pure and Applied Analysis, 2020, 19 (6) : 3341-3366. doi: 10.3934/cpaa.2020148 |
[10] |
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 |
[11] |
Weinan E, Jianfeng Lu. Mathematical theory of solids: From quantum mechanics to continuum models. Discrete and Continuous Dynamical Systems, 2014, 34 (12) : 5085-5097. doi: 10.3934/dcds.2014.34.5085 |
[12] |
Paolo Antonelli, Pierangelo Marcati. Quantum hydrodynamics with nonlinear interactions. Discrete and Continuous Dynamical Systems - S, 2016, 9 (1) : 1-13. doi: 10.3934/dcdss.2016.9.1 |
[13] |
Gabriel Rivière. Remarks on quantum ergodicity. Journal of Modern Dynamics, 2013, 7 (1) : 119-133. doi: 10.3934/jmd.2013.7.119 |
[14] |
Sergei Avdonin, Pavel Kurasov. Inverse problems for quantum trees. Inverse Problems and Imaging, 2008, 2 (1) : 1-21. doi: 10.3934/ipi.2008.2.1 |
[15] |
Dmitry Jakobson. On quantum limits on flat tori. Electronic Research Announcements, 1995, 1: 80-86. |
[16] |
James B. Kennedy, Jonathan Rohleder. On the hot spots of quantum graphs. Communications on Pure and Applied Analysis, 2021, 20 (9) : 3029-3063. doi: 10.3934/cpaa.2021095 |
[17] |
Jin-Cheng Jiang, Chi-Kun Lin, Shuanglin Shao. On one dimensional quantum Zakharov system. Discrete and Continuous Dynamical Systems, 2016, 36 (10) : 5445-5475. doi: 10.3934/dcds.2016040 |
[18] |
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 |
[19] |
Ruikuan Liu, Tian Ma, Shouhong Wang, Jiayan Yang. Thermodynamical potentials of classical and quantum systems. Discrete and Continuous Dynamical Systems - B, 2019, 24 (4) : 1411-1448. doi: 10.3934/dcdsb.2018214 |
[20] |
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 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]