Grovers algorithm is a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The Amplitude Amplification in Grovers algorithm is T = O(N). This paper intr...Grovers algorithm is a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The Amplitude Amplification in Grovers algorithm is T = O(N). This paper introduces two new algorithms for Amplitude Amplification in Grovers algorithm with a time complexity of T = O(logN), aiming to improve efficiency in quantum computing. The difference between Grovers algorithm and our first algorithm is that the Amplitude Amplification ratio in Grovers algorithm is an arithmetic series and ours, a geometric one. Because our Amplitude Amplification ratios converge much faster, the time complexity is improved significantly. In our second algorithm, we introduced a new concept, Amplitude Transfer where the marked state is transferred to a new set of qubits such that the new qubit state is an eigenstate of measurable variables. When the new qubit quantum state is measured, with high probability, the correct solution will be obtained.展开更多
We uncover the virtual monopoles underlying the nontrivial phases of the one-dimensional nonlinear excitations of rogue waves by extending the Dirac magnetic monopole theory to a complex plane. We find that the densit...We uncover the virtual monopoles underlying the nontrivial phases of the one-dimensional nonlinear excitations of rogue waves by extending the Dirac magnetic monopole theory to a complex plane. We find that the density zeros of the nonlinear waves on the extended complex plane constitute the virtual monopole fields with a quantized flux of elementary π. We then explain the exotic properties of rogue waves by means of a virtual monopole collision mechanism and find that the maximum amplitude amplification ratio and multiple phase steps of the high-order rogue waves are closely related to the number of their contained monopoles. These results open a new avenue for studying topological properties of nonlinear waves and provide an alternative way to understand their dynamics.展开更多
Neighborhood preserving embedding(NPE)is an important linear dimensionality reduction technique that aims at preserving the local manifold structure.NPE contains three steps,i.e.,finding the nearest neighbors of each ...Neighborhood preserving embedding(NPE)is an important linear dimensionality reduction technique that aims at preserving the local manifold structure.NPE contains three steps,i.e.,finding the nearest neighbors of each data point,constructing the weight matrix,and obtaining the transformation matrix.Liang et al.proposed a variational quantum algorithm(VQA)for NPE[Phys.Rev.A 101032323(2020)].The algorithm consists of three quantum sub-algorithms,corresponding to the three steps of NPE,and was expected to have an exponential speedup on the dimensionality n.However,the algorithm has two disadvantages:(i)It is not known how to efficiently obtain the input of the third sub-algorithm from the output of the second one.(ii)Its complexity cannot be rigorously analyzed because the third sub-algorithm in it is a VQA.In this paper,we propose a complete quantum algorithm for NPE,in which we redesign the three sub-algorithms and give a rigorous complexity analysis.It is shown that our algorithm can achieve a polynomial speedup on the number of data points m and an exponential speedup on the dimensionality n under certain conditions over the classical NPE algorithm,and achieve a significant speedup compared to Liang et al.’s algorithm even without considering the complexity of the VQA.展开更多
This paper provides an introduction to a quantum search algorithm,known as Grover’s Algorithm,for unsorted search purposes.The algorithm is implemented in a search space of 4 qubits using the Python-based Qiskit SDK ...This paper provides an introduction to a quantum search algorithm,known as Grover’s Algorithm,for unsorted search purposes.The algorithm is implemented in a search space of 4 qubits using the Python-based Qiskit SDK by IBM.While providing detailed proof,the computational complexity of the algorithm is generalized to n qubits.The implementation results obtained from the IBM QASM Simulator and IBMQ Santiago quantum backend are analyzed and compared.Finally,the paper discusses the challenges faced in implementation and real-life applications of the algorithm hitherto.Overall,the implementation and analysis depict the advantages of this quantum search algorithm over its classical counterparts.展开更多
Since Grover’s algorithm was first introduced, it has become a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The original application was the uns...Since Grover’s algorithm was first introduced, it has become a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The original application was the unstructured search problems with the time complexity of O(). In Grover’s algorithm, the key is Oracle and Amplitude Amplification. In this paper, our purpose is to show through examples that, in general, the time complexity of the Oracle Phase is O(N), not O(1). As a result, the time complexity of Grover’s algorithm is O(N), not O(). As a secondary purpose, we also attempt to restore the time complexity of Grover’s algorithm to its original form, O(), by introducing an O(1) parallel algorithm for unstructured search without repeated items, which will work for most cases. In the worst-case scenarios where the number of repeated items is O(N), the time complexity of the Oracle Phase is still O(N) even after additional preprocessing.展开更多
The quantum security of lightweight block ciphers is receiving more and more attention.However,the existing quantum attacks on lightweight block ciphers only focused on the quantum exhaustive search,while the quantum ...The quantum security of lightweight block ciphers is receiving more and more attention.However,the existing quantum attacks on lightweight block ciphers only focused on the quantum exhaustive search,while the quantum attacks combined with classical cryptanalysis methods haven’t been well studied.In this paper,we study quantum key recovery attack on SIMON32/64 using Quantum Amplitude Amplification algorithm in Q1 model.At first,we reanalyze the quantum circuit complexity of quantum exhaustive search on SIMON32/64.We estimate the Clifford gates count more accurately and reduce the T gate count.Also,the T-depth and full depth is reduced due to our minor modifications.Then,using four differentials given by Biryukov in FSE 2014 as our distinguisher,we give our quantum key recovery attack on 19-round SIMON32/64.We treat the two phases of key recovery attack as two QAA instances separately,and the first QAA instance consists of four sub-QAA instances.Then,we design the quantum circuit of these two QAA instances and estimate their corresponding quantum circuit complexity.We conclude that the quantum circuit of our quantum key recovery attack is lower than quantum exhaustive search.Our work firstly studies the quantum dedicated attack on SIMON32/64.And this is the first work to study the complexity of quantum dedicated attacks from the perspective of quantum circuit complexity,which is a more fine-grained analysis of quantum dedicated attacks’complexity.展开更多
文摘Grovers algorithm is a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The Amplitude Amplification in Grovers algorithm is T = O(N). This paper introduces two new algorithms for Amplitude Amplification in Grovers algorithm with a time complexity of T = O(logN), aiming to improve efficiency in quantum computing. The difference between Grovers algorithm and our first algorithm is that the Amplitude Amplification ratio in Grovers algorithm is an arithmetic series and ours, a geometric one. Because our Amplitude Amplification ratios converge much faster, the time complexity is improved significantly. In our second algorithm, we introduced a new concept, Amplitude Transfer where the marked state is transferred to a new set of qubits such that the new qubit state is an eigenstate of measurable variables. When the new qubit quantum state is measured, with high probability, the correct solution will be obtained.
基金supported by the National Natural Science Foundation of China (Grant Nos.12375005,12022513,and12235007)the National Safety Academic Fund(Grant No.U2330401)。
文摘We uncover the virtual monopoles underlying the nontrivial phases of the one-dimensional nonlinear excitations of rogue waves by extending the Dirac magnetic monopole theory to a complex plane. We find that the density zeros of the nonlinear waves on the extended complex plane constitute the virtual monopole fields with a quantized flux of elementary π. We then explain the exotic properties of rogue waves by means of a virtual monopole collision mechanism and find that the maximum amplitude amplification ratio and multiple phase steps of the high-order rogue waves are closely related to the number of their contained monopoles. These results open a new avenue for studying topological properties of nonlinear waves and provide an alternative way to understand their dynamics.
基金supported by the Fundamental Research Funds for the Central Universities(Grant No.2019XD-A01)the National Natural Science Foundation of China(Grant Nos.61972048 and 61976024)。
文摘Neighborhood preserving embedding(NPE)is an important linear dimensionality reduction technique that aims at preserving the local manifold structure.NPE contains three steps,i.e.,finding the nearest neighbors of each data point,constructing the weight matrix,and obtaining the transformation matrix.Liang et al.proposed a variational quantum algorithm(VQA)for NPE[Phys.Rev.A 101032323(2020)].The algorithm consists of three quantum sub-algorithms,corresponding to the three steps of NPE,and was expected to have an exponential speedup on the dimensionality n.However,the algorithm has two disadvantages:(i)It is not known how to efficiently obtain the input of the third sub-algorithm from the output of the second one.(ii)Its complexity cannot be rigorously analyzed because the third sub-algorithm in it is a VQA.In this paper,we propose a complete quantum algorithm for NPE,in which we redesign the three sub-algorithms and give a rigorous complexity analysis.It is shown that our algorithm can achieve a polynomial speedup on the number of data points m and an exponential speedup on the dimensionality n under certain conditions over the classical NPE algorithm,and achieve a significant speedup compared to Liang et al.’s algorithm even without considering the complexity of the VQA.
文摘This paper provides an introduction to a quantum search algorithm,known as Grover’s Algorithm,for unsorted search purposes.The algorithm is implemented in a search space of 4 qubits using the Python-based Qiskit SDK by IBM.While providing detailed proof,the computational complexity of the algorithm is generalized to n qubits.The implementation results obtained from the IBM QASM Simulator and IBMQ Santiago quantum backend are analyzed and compared.Finally,the paper discusses the challenges faced in implementation and real-life applications of the algorithm hitherto.Overall,the implementation and analysis depict the advantages of this quantum search algorithm over its classical counterparts.
文摘Since Grover’s algorithm was first introduced, it has become a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The original application was the unstructured search problems with the time complexity of O(). In Grover’s algorithm, the key is Oracle and Amplitude Amplification. In this paper, our purpose is to show through examples that, in general, the time complexity of the Oracle Phase is O(N), not O(1). As a result, the time complexity of Grover’s algorithm is O(N), not O(). As a secondary purpose, we also attempt to restore the time complexity of Grover’s algorithm to its original form, O(), by introducing an O(1) parallel algorithm for unstructured search without repeated items, which will work for most cases. In the worst-case scenarios where the number of repeated items is O(N), the time complexity of the Oracle Phase is still O(N) even after additional preprocessing.
基金National Natural Science Foundation of China(Grant No.61672517)National Natural Foundation of China(Key program,Grant No.61732021)+1 种基金National Cyrptography Development Fund(Grant No.MMJJ20170108)Beijing Municipal Science&Technology Commission(Grant No.Z191100007119006).
文摘The quantum security of lightweight block ciphers is receiving more and more attention.However,the existing quantum attacks on lightweight block ciphers only focused on the quantum exhaustive search,while the quantum attacks combined with classical cryptanalysis methods haven’t been well studied.In this paper,we study quantum key recovery attack on SIMON32/64 using Quantum Amplitude Amplification algorithm in Q1 model.At first,we reanalyze the quantum circuit complexity of quantum exhaustive search on SIMON32/64.We estimate the Clifford gates count more accurately and reduce the T gate count.Also,the T-depth and full depth is reduced due to our minor modifications.Then,using four differentials given by Biryukov in FSE 2014 as our distinguisher,we give our quantum key recovery attack on 19-round SIMON32/64.We treat the two phases of key recovery attack as two QAA instances separately,and the first QAA instance consists of four sub-QAA instances.Then,we design the quantum circuit of these two QAA instances and estimate their corresponding quantum circuit complexity.We conclude that the quantum circuit of our quantum key recovery attack is lower than quantum exhaustive search.Our work firstly studies the quantum dedicated attack on SIMON32/64.And this is the first work to study the complexity of quantum dedicated attacks from the perspective of quantum circuit complexity,which is a more fine-grained analysis of quantum dedicated attacks’complexity.
