We have proposed a primal-dual fixed point algorithm （PDFP） for solving minimiza- tion of the sum of three convex separable functions, which involves a smooth function with Lipschitz continuous gradient, a linear co...We have proposed a primal-dual fixed point algorithm （PDFP） for solving minimiza- tion of the sum of three convex separable functions, which involves a smooth function with Lipschitz continuous gradient, a linear composite nonsmooth function, and a nonsmooth function. Compared with similar works, the parameters in PDFP are easier to choose and are allowed in a relatively larger range. We will extend PDFP to solve two kinds of separable multi-block minimization problems, arising in signal processing and imaging science. This work shows the flexibility of applying PDFP algorithm to multi-block prob- lems and illustrates how practical and fully splitting schemes can be derived, especially for parallel implementation of large scale problems. The connections and comparisons to the alternating direction method of multiplier （ADMM） are also present. We demonstrate how different algorithms can be obtained by splitting the problems in different ways through the classic example of sparsity regularized least square model with constraint. In particular, for a class of linearly constrained problems, which are of great interest in the context of multi-block ADMM, can be also solved by PDFP with a guarantee of convergence. Finally, some experiments are provided to illustrate the performance of several schemes derived by the PDFP algorithm.展开更多
This paper presents a quantum algorithm to decide whether a Boolean equation system F has a solution and to compute one if F does have solutions with any given success probability.The runtime complexity of the algorit...This paper presents a quantum algorithm to decide whether a Boolean equation system F has a solution and to compute one if F does have solutions with any given success probability.The runtime complexity of the algorithm is polynomial in the size of F and the condition number of certain Macaulay matrix associated with F.As a consequence,the authors give a polynomial-time quantum algorithm for solving Boolean equation systems if their condition numbers are polynomial in the size of F.The authors apply the proposed quantum algorithm to the cryptanalysis of several important cryptosystems:The stream cipher Trivum,the block cipher AES,the hash function SHA-3/Keccak,the multivariate public key cryptosystems,and show that they are secure under quantum algebraic attack only if the corresponding condition numbers are large.This leads to a new criterion for designing such cryptosystems which are safe against the attack of quantum computers:The corresponding condition number.展开更多
文摘We have proposed a primal-dual fixed point algorithm （PDFP） for solving minimiza- tion of the sum of three convex separable functions, which involves a smooth function with Lipschitz continuous gradient, a linear composite nonsmooth function, and a nonsmooth function. Compared with similar works, the parameters in PDFP are easier to choose and are allowed in a relatively larger range. We will extend PDFP to solve two kinds of separable multi-block minimization problems, arising in signal processing and imaging science. This work shows the flexibility of applying PDFP algorithm to multi-block prob- lems and illustrates how practical and fully splitting schemes can be derived, especially for parallel implementation of large scale problems. The connections and comparisons to the alternating direction method of multiplier （ADMM） are also present. We demonstrate how different algorithms can be obtained by splitting the problems in different ways through the classic example of sparsity regularized least square model with constraint. In particular, for a class of linearly constrained problems, which are of great interest in the context of multi-block ADMM, can be also solved by PDFP with a guarantee of convergence. Finally, some experiments are provided to illustrate the performance of several schemes derived by the PDFP algorithm.
基金supported by the National Natural Science Foundation of China under Grant No.11688101and NKRDP 2018YFA0704705。
文摘This paper presents a quantum algorithm to decide whether a Boolean equation system F has a solution and to compute one if F does have solutions with any given success probability.The runtime complexity of the algorithm is polynomial in the size of F and the condition number of certain Macaulay matrix associated with F.As a consequence,the authors give a polynomial-time quantum algorithm for solving Boolean equation systems if their condition numbers are polynomial in the size of F.The authors apply the proposed quantum algorithm to the cryptanalysis of several important cryptosystems:The stream cipher Trivum,the block cipher AES,the hash function SHA-3/Keccak,the multivariate public key cryptosystems,and show that they are secure under quantum algebraic attack only if the corresponding condition numbers are large.This leads to a new criterion for designing such cryptosystems which are safe against the attack of quantum computers:The corresponding condition number.
