The well-known Riccati differential equations play a key role in many fields,including problems in protein folding,control and stabilization,stochastic control,and cybersecurity(risk analysis and malware propaga-tion)...The well-known Riccati differential equations play a key role in many fields,including problems in protein folding,control and stabilization,stochastic control,and cybersecurity(risk analysis and malware propaga-tion).Quantum computer algorithms have the potential to implement faster approximate solutions to the Riccati equations compared with strictly classical algorithms.While systems with many qubits are still under development,there is significant interest in developing algorithms for near-term quantum computers to determine their accuracy and limitations.In this paper,we propose a hybrid quantum-classical algorithm,the Matrix Riccati Solver(MRS).This approach uses a transformation of variables to turn a set of nonlinear differential equation into a set of approximate linear differential equations(i.e.,second order non-constant coefficients)which can in turn be solved using a version of the Harrow-Hassidim-Lloyd(HHL)quantum algorithm for the case of Hermitian matrices.We implement this approach using the Qiskit language and compute near-term results using a 4 qubit IBM Q System quantum computer.Comparisons with classical results and areas for future research are discussed.展开更多
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.展开更多
文摘The well-known Riccati differential equations play a key role in many fields,including problems in protein folding,control and stabilization,stochastic control,and cybersecurity(risk analysis and malware propaga-tion).Quantum computer algorithms have the potential to implement faster approximate solutions to the Riccati equations compared with strictly classical algorithms.While systems with many qubits are still under development,there is significant interest in developing algorithms for near-term quantum computers to determine their accuracy and limitations.In this paper,we propose a hybrid quantum-classical algorithm,the Matrix Riccati Solver(MRS).This approach uses a transformation of variables to turn a set of nonlinear differential equation into a set of approximate linear differential equations(i.e.,second order non-constant coefficients)which can in turn be solved using a version of the Harrow-Hassidim-Lloyd(HHL)quantum algorithm for the case of Hermitian matrices.We implement this approach using the Qiskit language and compute near-term results using a 4 qubit IBM Q System quantum computer.Comparisons with classical results and areas for future research are discussed.
基金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.