Advances in quantum computers threaten to break public key cryptosystems such as RSA, ECC, and EIGamal on the hardness of factoring or taking a discrete logarithm, while no quantum algorithms are found to solve certai...Advances in quantum computers threaten to break public key cryptosystems such as RSA, ECC, and EIGamal on the hardness of factoring or taking a discrete logarithm, while no quantum algorithms are found to solve certain mathematical problems on non-commutative algebraic structures until now. In this background, Majid Khan et al.proposed two novel public-key encryption schemes based on large abelian subgroup of general linear group over a residue ring. In this paper we show that the two schemes are not secure. We present that they are vulnerable to a structural attack and that, it only requires polynomial time complexity to retrieve the message from associated public keys respectively. Then we conduct a detailed analysis on attack methods and show corresponding algorithmic description and efficiency analysis respectively. After that, we propose an improvement assisted to enhance Majid Khan's scheme. In addition, we discuss possible lines of future work.展开更多
Based on the estimating rule of the normal vector angles between two adjacent terrain units, we use the concept of terrain complexity factor to quantify the terrain complexity of DEM, and then the formula of terrain c...Based on the estimating rule of the normal vector angles between two adjacent terrain units, we use the concept of terrain complexity factor to quantify the terrain complexity of DEM, and then the formula of terrain complexity factor in Raster DEM and TIN DEM is deduced theoretically. In order to make clear how the terrain complexity factor ECF and the average elevation h affect the accuracy of DEM terrain representation RMSEEt, the formula of Gauss synthetical surface is applied to simulate several real terrain surfaces, each of which has different terrain complexity. Through the statistical analysis of linear regression in simula- tion data, the linear equation between accuracy of DEM terrain representation RMSEEt, terrain complexity factor ECF and the average elevation h is achieved. A new method is provided to estimate the accuracy of DEM terrain representation RMSEEt with a certain terrain complexity and it gives convincing theoretical evidence for DEM production and the corresponding error research in the future.展开更多
In this context,we study three different strategies to improve the time complexity of the widely used adiabatic evolution algorithms when solving a particular class of quantum search problems where both the initial an...In this context,we study three different strategies to improve the time complexity of the widely used adiabatic evolution algorithms when solving a particular class of quantum search problems where both the initial and final Hamiltonians are one-dimensional projector Hamiltonians on the corresponding ground state.After some simple analysis,we find the time complexity improvement is always accompanied by the increase of some other "complexities" that should be considered.But this just gives the implication that more feasibilities can be achieved in adiabatic evolution based quantum algorithms over the circuit model,even though the equivalence between the two has been shown.In addition,we also give a rough comparison between these different models for the speedup of the problem.展开更多
In this paper,we study two different nonlinear interpolating paths in adiabatic evolution algorithms for solving a particular class of quantum search problems where both the initial and final Hamiltonian are one-dimen...In this paper,we study two different nonlinear interpolating paths in adiabatic evolution algorithms for solving a particular class of quantum search problems where both the initial and final Hamiltonian are one-dimensional projector Hamiltonians on the corresponding ground state.If the overlap between the initial state and final state of the quantum system is not equal to zero,both of these models can provide a constant time speedup over the usual adiabatic algorithms by increasing some another corresponding "complexity".But when the initial state has a zero overlap with the solution state in the problem,the second model leads to an infinite time complexity of the algorithm for whatever interpolating functions being applied while the first one can still provide a constant running time.However,inspired by a related reference,a variant of the first model can be constructed which also fails for the problem when the overlap is exactly equal to zero if we want to make up the "intrinsic" fault of the second model - an increase in energy.Two concrete theorems are given to serve as explanations why neither of these two models can improve the usual adiabatic evolution algorithms for the phenomenon above.These just tell us what should be noted when using certain nonlinear evolution paths in adiabatic quantum algorithms for some special kind of problems.展开更多
基金supported in part by the National Natural Science Foundation of China(Grant Nos.61303212,61170080,61202386)the State Key Program of National Natural Science of China(Grant Nos.61332019,U1135004)+2 种基金the Major Research Plan of the National Natural Science Foundation of China(Grant No.91018008)Major State Basic Research Development Program of China(973 Program)(No.2014CB340600)the Hubei Natural Science Foundation of China(Grant Nos.2011CDB453,2014CFB440)
文摘Advances in quantum computers threaten to break public key cryptosystems such as RSA, ECC, and EIGamal on the hardness of factoring or taking a discrete logarithm, while no quantum algorithms are found to solve certain mathematical problems on non-commutative algebraic structures until now. In this background, Majid Khan et al.proposed two novel public-key encryption schemes based on large abelian subgroup of general linear group over a residue ring. In this paper we show that the two schemes are not secure. We present that they are vulnerable to a structural attack and that, it only requires polynomial time complexity to retrieve the message from associated public keys respectively. Then we conduct a detailed analysis on attack methods and show corresponding algorithmic description and efficiency analysis respectively. After that, we propose an improvement assisted to enhance Majid Khan's scheme. In addition, we discuss possible lines of future work.
基金Supported by Innovation Program of Shanghai Municipal Education Commission (No.10ZZ25)the Key Laboratory of Geo-informatics of State Bureau of Surveying and Mapping (No.200914)
文摘Based on the estimating rule of the normal vector angles between two adjacent terrain units, we use the concept of terrain complexity factor to quantify the terrain complexity of DEM, and then the formula of terrain complexity factor in Raster DEM and TIN DEM is deduced theoretically. In order to make clear how the terrain complexity factor ECF and the average elevation h affect the accuracy of DEM terrain representation RMSEEt, the formula of Gauss synthetical surface is applied to simulate several real terrain surfaces, each of which has different terrain complexity. Through the statistical analysis of linear regression in simula- tion data, the linear equation between accuracy of DEM terrain representation RMSEEt, terrain complexity factor ECF and the average elevation h is achieved. A new method is provided to estimate the accuracy of DEM terrain representation RMSEEt with a certain terrain complexity and it gives convincing theoretical evidence for DEM production and the corresponding error research in the future.
基金supported by the National Natural Science Foundation of China (Grant No. 61173050)
文摘In this context,we study three different strategies to improve the time complexity of the widely used adiabatic evolution algorithms when solving a particular class of quantum search problems where both the initial and final Hamiltonians are one-dimensional projector Hamiltonians on the corresponding ground state.After some simple analysis,we find the time complexity improvement is always accompanied by the increase of some other "complexities" that should be considered.But this just gives the implication that more feasibilities can be achieved in adiabatic evolution based quantum algorithms over the circuit model,even though the equivalence between the two has been shown.In addition,we also give a rough comparison between these different models for the speedup of the problem.
基金Supported by the National Natural Science Foundation of China under Grant No. 61173050
文摘In this paper,we study two different nonlinear interpolating paths in adiabatic evolution algorithms for solving a particular class of quantum search problems where both the initial and final Hamiltonian are one-dimensional projector Hamiltonians on the corresponding ground state.If the overlap between the initial state and final state of the quantum system is not equal to zero,both of these models can provide a constant time speedup over the usual adiabatic algorithms by increasing some another corresponding "complexity".But when the initial state has a zero overlap with the solution state in the problem,the second model leads to an infinite time complexity of the algorithm for whatever interpolating functions being applied while the first one can still provide a constant running time.However,inspired by a related reference,a variant of the first model can be constructed which also fails for the problem when the overlap is exactly equal to zero if we want to make up the "intrinsic" fault of the second model - an increase in energy.Two concrete theorems are given to serve as explanations why neither of these two models can improve the usual adiabatic evolution algorithms for the phenomenon above.These just tell us what should be noted when using certain nonlinear evolution paths in adiabatic quantum algorithms for some special kind of problems.
