Search

The parallel computing power of quantum computing and the special properties of qubits provide an effective solution for image processing tasks. This paper presents a quantum image encryption algorithm based on Fisher–Yates algorithm and Logistic mapping. Firstly, the Fisher–Yates algorithm is used to generate three key sequences, one of which is used to encode the coordinate qubits of the image. Using the other two keys and the preset rules, the quantum coordinate scrambling operation is designed based on the encoded coordinate qubit, which effectively scrambles the spatial information of the plaintext image. Next, another set of key sequences is generated, one of which is used to encode the color qubits of the image. Using two other key sequences and different rules, a qubit plane scrambling operation based on coded color qubits is designed, and the color information of image is scrambled successfully. Finally, the quantum key image is generated based on Logistic mapping, and the key image is scrambled based on Fisher–Yates algorithm to improve the key complexity. The final ciphertext image is obtained by performing XOR operation between the original image and the scrambled key image. The complete quantum circuit diagram of the scheme is given in this paper. The experimental results and security analysis prove the effectiveness of the scheme, which provides a large key space and the computational complexity is only O(n). [ABSTRACT FROM AUTHOR]

The foundation of this research is the quantum implementation of two hashing algorithms, namely Secure Hash Algorithm (SHA1) and Message Digest (MD5). Quantum cryptography is a challenging topic in network security for future networks. Quantum cryptography is an outgrowth of two broad topics—cryptology and cryptanalysis. In this paper, SHA1 and MD5 algorithms are designed and implemented for quantum computers. The main aim is to study and investigate the time requirement to build a hash and the bit rate at which a hash value is sent through. In this paper, a comprehensive analysis of these two algorithms is performed. Experiments have been done to compare and contrast the performances of the classical and proposed algorithms. In the experiment, it was found that the total time of execution of quantum SHA1 and quantum MD5 is much higher than the classical SHA1 and MD5. During quantum MD5 execution, it is observed that the time doubles when the number of chunks is increased from 1 to 2. Another experimental observation is that the execution time of the implemented algorithms depends upon the processor's speed. [ABSTRACT FROM AUTHOR]

Since Grover developed a quantum search algorithm for unstructured data, generalizing the algorithm to structured datasets, which can be represented as graphs, has been an important research topic. Recently, Krovi et al. introduced a quantum algorithm that can find a marked vertex on any ergodic and reversible graph by using absorbing marked vertices, replacing the marked vertices with partially absorbing vertices. The algorithm was extended to finding marked vertices in any graph with multiple marked vertices using the quantum fast-forwarding technique (QFF). However, the proof of this result based on QFF does not provide much intuition about the underlying mechanism. In this paper, to obtain the underlying mechanism of the quantum search with absorbing marked vertices, we consider, as a nontrivial example, the complete bipartite graph consisting of two sets X 1 and X 2 with the marked vertices being on both vertex sets. By analytically finding the spectral information of the quantum walk, we propose an approximate optimal search parameter s o . We demonstrate that the quantum algorithm at the optimal search parameter s o shows a quadratic speedup compared to the corresponding classical search method if the number of marked vertices is smaller than the total number of vertices. Additionally, we find that the quantum search is described in terms of a two-state model for that case. [ABSTRACT FROM AUTHOR]

Quantum computing has made many important achievements in the field of cryptanalysis. However, due to the limitations of current physical system and technology, the realization of large-scale universal quantum computers is a long way off. Currently, small-scale quantum computers are easier to implement than large-scale universal quantum computers. Distributed quantum computing proposes an implementation architecture, which attempts to break down large-scale tasks into many sub-tasks distributed across multiple small-scale quantum computers. How to use small-scale quantum computers with fewer qubits and shallower quantum depths to complete large-scale tasks and improve the success rate of attacking symmetric cryptosystems is our concern. In this paper, we propose a distributed exact Simon's algorithm, apply it to achieve quantum key recovery attacks on single-permutation-based pseudorandom cryptographic schemes with classical birthday bound security, and estimate the quantum resources of quantum circuits. Furthermore, we combine distributed exact Grover's algorithm and distributed exact Simon's algorithm to achieve quantum key recovery attacks on two-permutation-based pseudorandom cryptographic schemes with classical beyond birthday bound security and estimate the corresponding quantum resources. Our results show that (1) our algorithms are exact which means that the theoretical success probability of attacking pseudorandom cryptographic schemes is 100%; (2) the depth of circuit is in polynomial time which means that the theoretical depth of attacking symmetric cryptosystems is exponentially accelerated relative to the previous results; (3) the qubits of circuit don't increase significantly. Our work is of great importance. It could lead to the rapid realization of effective quantum attacks against symmetric cryptosystems on small-scale quantum computers. [ABSTRACT FROM AUTHOR]

In the domain of quantum computing, two widely employed techniques for encoding a normalized vector of length N, denoted as { α i } , are one-hot encoding and binary encoding. The one-hot encoding state is represented as | ψ OH (N) ⟩ and can be expressed as: | ψ OH (N) ⟩ = ∑ i = 0 N - 1 α i | 0 ⟩ ⊗ N - i - 1 | 1 ⟩ | 0 ⟩ ⊗ i . On the other hand, the binary encoding state is symbolized as | ψ BI (N) ⟩ and is defined as: | ψ BI (N) ⟩ = ∑ i = 0 N - 1 α i | b i ⟩ , where b i corresponds to the binary representation of i. In this paper, we introduce a method for converting between the one-hot encoding state and the binary encoding state, utilizing the Domain Wall state as an intermediary. The Domain Wall state, denoted as | ψ DW (N) ⟩ , is defined as: | ψ DW (N) ⟩ = ∑ i = 0 N - 1 α i | 0 ⟩ ⊗ N - i - 1 | 1 ⟩ ⊗ i . Our proposed circuit achieves a depth of O (log 2 N) and a size of O(N).Kindly check and confirm that the corresponding author mail id is correctly identified. [ABSTRACT FROM AUTHOR]

The quantum phase estimation algorithm has been utilized by a variety of quantum algorithms, most notably Shor's algorithm, to obtain information regarding the period of a function that is appropriately encoded into a unitary operator. In many cases, it is desired to estimate whether a specific state exhibits a certain pattern quickly. In this paper, we exhibit a methodology based on the QPE algorithm to identify certain patterns. In particular, starting from a properly encoded state, we demonstrate how to construct unitary operators whose eigenvectors correspond to states with proper diagonals. QPE will then output an eigenphase equal to zero with certainty for these states, thereby identifying this class of matrices. For partial matches, our algorithm, based on the tolerance threshold used, will show areas of high similarity, and it will outperform classical ones when the number of mismatches defined by the tolerance is significantly low when compared to the size of the diagonal. [ABSTRACT FROM AUTHOR]

A recent paper (Quantum Info. Process 16.9, 2017) proposes a classical framework named Quantum Simulation Logic (QSL) capable of an efficient classical simulation of Deutsch–Jozsa and Simon algorithms. In this comment, we show instances of the Deutsch–Jozsa (DJ) and the Simon quantum algorithms that generate incorrect results with the QSL version, contradicting the proposal and the main results of the original paper. [ABSTRACT FROM AUTHOR]

Clustering, a well-studied problem in the machine learning community, becomes even more intriguing with the emergence of quantum machine learning. Specifically, exploring clustering techniques for quantum data, such as quantum states, holds great interest. This paper introduces a quantum state clustering algorithm that utilizes variational quantum circuits. Our algorithm transforms the clustering problem into a parameter optimization task involving parametric quantum circuits. Each cluster is represented by a variational quantum circuit (VQC), which learns to extract the distinctive feature of its corresponding cluster during the optimization process. To guide the optimization of circuit parameters, we design an objective function that encourages each cluster's feature extractor to produce features similar to states within its own cluster and dissimilar to states in other clusters. We construct four quantum state datasets for testing the effectiveness of our algorithm. The numerical results demonstrate that our algorithm can achieve satisfying performance. [ABSTRACT FROM AUTHOR]

Quantum multidimensional scaling is a quantum dimensionality reduction algorithm. Its complex quantum circuit design structure and excessive qubits consumption make it difficult to run on the current quantum computers. In order to solve this problem, this paper proposes the variational quantum multidimensional scaling algorithm based on the variational quantum algorithm. Utilizing the parallel advantages of quantum computing to quickly compute low-dimensional embeddings of high-dimensional data, the variational quantum multidimensional scaling algorithm can provide lower time complexity; compared with the non-variational quantum multidimensional scaling algorithm, the variational quantum multidimensional scaling algorithm provides a simpler quantum circuit. In the noisy intermediate scale quantum era, the algorithm can run on a quantum computer. In addition, the article finally implemented the variational quantum multidimensional scaling algorithm on the Qiskit framework, proving the correctness of the algorithm. [ABSTRACT FROM AUTHOR]

Quantum approximate optimization algorithms are hybrid quantum-classical variational algorithms designed to approximately solve combinatorial optimization problems such as the MAX-CUT problem. In spite of its potential for near-term quantum applications, it has been known that quantum approximate optimization algorithms have limitations for certain instances to solve the MAX-CUT problem, at any constant level p. Recently, the recursive quantum approximate optimization algorithm, which is a non-local version of quantum approximate optimization algorithm, has been proposed to overcome these limitations. However, it has been shown by mostly numerical evidences that the recursive quantum approximate optimization algorithm outperforms the original quantum approximate optimization algorithm for specific instances. In this paper, we analytically prove that the recursive quantum approximate optimization algorithm is more competitive than the original one to solve the MAX-CUT problem for complete graphs with respect to the approximation ratio. [ABSTRACT FROM AUTHOR]

Data mining has reached a state that is difficult to break through, while the scale of data is growing rapidly, due to the lack of traditional computing power and limited data storage space. Efficient and accurate extraction of valuable information from massive data has become a challenge. Researchers have combined quantum computing with data mining to address this problem, hence the concept of quantum data mining has emerged. The fundamental tenets of quantum physics are adhered to for information transmission and computing operations in quantum data mining, which use the states of minuscule particles to represent and process information. Quantum data mining are based on the characteristics of quantum computing, such as superposition and entanglement, which make the ability of computational and information extraction effectively improved. The paper discusses and summarizes the relevant literature on quantum data mining in recent 3 years. After introducing relevant basic concepts of quantum computing, quantum data mining is presented in five aspects: quantum data classification, quantum data clustering, quantum dimensionality reduction, quantum association rules, quantum linear regression, and quantum causal analysis. These approaches, based on quantum computing, offer new perspectives and tools for handling complex data mining tasks. In conclusion, the development of quantum data mining is promising and crucial to overcome the difficulties associated with large-scale data mining. [ABSTRACT FROM AUTHOR]

Popular Secp256k1 and Schnorr algorithms offer strong security in current Blockchains. However, they are vulnerable to quantum attacks. To solve this problem, several quantum-resistant algorithms have been proposed. However, the performance evaluations and tangible analyses of these algorithms on current Blockchains have not been studied yet. In this context, a performance analysis of quantum-resistant algorithms on a Blockchain can provide valuable insight into the efficiency of quantum-resistant algorithms in real-world scenarios. To address this need, we prototyped and analyzed a quantum-resistant Blockchain using the Falcon algorithm. Falcon is selected because it provides smaller signature and key size compared to Crystals-Dilithium and Sphincs+. We then measured in real-time the key size, transaction signature size, and transaction verification time. The paper also discusses the potential scalability limitations of the proposed quantum-resistant Blockchain and suggests an approach to select quantum-resistant algorithms based on different Blockchain use cases. Our approach and benchmark results have implications for the future development and adoption of quantum-resistant Blockchains. [ABSTRACT FROM AUTHOR]

Finding solutions to systems of linear equations is a common problem in many areas of science and engineering, with much potential for a speed up on quantum devices. While the Harrow–Hassidim–Lloyd (HHL) quantum algorithm yields up to an exponential speed up over classical algorithms in some cases, it requires a fault-tolerant quantum computer, which is unlikely to be available in the near-term. Thus, attention has turned to the investigation of quantum algorithms for noisy intermediate-scale quantum (NISQ) devices where several near-term approaches to solving systems of linear equations have been proposed. This paper focuses on the Variational Quantum Linear Solvers (VQLS), and other closely related methods and adaptions. Several contributions are made in this paper, which include: the first application of the Evolutionary Ansatz to the VQLS (EAVQLS), the first implementation of the Logical Ansatz VQLS (LAVQLS), based on the Classical Combination of Quantum States (CQS) method, a proof of principle demonstration of the CQS method on real quantum hardware and a method for the implementation of the Adiabatic Ansatz on the VQLS (AAVQLS). These approaches are implemented and contrasted. The CQS method is run with moderate success on a real quantum device. The EAVQLS and AAVQLS show promise as possible improvements to the standard VQLS algorithm once refined. [ABSTRACT FROM AUTHOR]

With the development of noisy intermediate-scale quantum machines, quantum processors show their supremacy in specific applications. To better understand the quantum behavior and verify larger quantum bit (qubit) algorithms, simulation on classical computers becomes crucial. However, as the simulated number of qubits increases, the full-state simulation suffers exponential memory increment for state vector storing. In order to compress the state vector, some existing works reduce the memory by data encoding compressors. Nevertheless, the memory requirement remains massive. Meanwhile, others utilize compact decision diagrams (DD) to represent the state vector, which only demands linear memory size. However, the existing DD-based simulation algorithm possesses many redundant calculations that require further exploration. Besides, the traditional normalization-based nodes merging method of DD amplifies the side influences of approximate error. Therefore, to tackle the above challenges, in this paper, we first fully explore the redundancies in the recursive-based DD simulation (RecurSim) algorithm. Inspired by the regularities of the quantum circuit model, a scale-based simulation (ScaleSim) algorithm is proposed, which removes plenty of unnecessary computations. Furthermore, to eliminate the influences of approximate error, we propose a new pre-check DD building method, namely PCB, which maintains the accuracy of DD representation and produces more memory saving. Comprehensive experiments show that our method achieves up to 24124.2 × acceleration and 3.2 × 10 7 × memory reduction than traditional DD-based methods on quantum algorithms while maintaining the representation accuracy. [ABSTRACT FROM AUTHOR]

The model of superposition queries in symmetric cryptanalysis has yielded remarkable results, such as Simon's period-finding algorithm, which can break many constructions in polynomial time. However, due to limitations of current physical devices, quantum circuits with long depths are often noisy and difficult to realize in practice. The novel computing architecture of distributed quantum computing is expected to reduce the noise and depth of quantum circuits. In this paper, we propose an offline algorithm model that combines distributed Simon's and Grover's algorithms. This model enables us to perform key recovery attacks on different rounds Feistel structures, Even Mansour construction, and the FX construction, while minimizing the quantum query complexity. Despite being limited to classical queries and offline quantum computations, we leverage the algebraic structure of cryptosystems to achieve successful key recovery attacks. [ABSTRACT FROM AUTHOR]

This paper presents an improved quantum dialogue protocol based on the HHL algorithm. In this protocol, Alice and Bob want to transmit their classical information to each other. Combining the HHL algorithm and quantum linear equation ensures that eavesdroppers cannot steal the data of communicators. In addition, communicators will connect come HHL quantum circuit constructed in this scheme with the swap test circuit to calculate the solution rather than directly measuring the result, which can improve the solution speed. Security analysis shows that this scheme is more secure than other general quantum dialogue schemes, and it can realize information protection in extreme cases, with good security and higher transmission efficiency. [ABSTRACT FROM AUTHOR]

Corners are very important local features for an image that can be widely used in many image processing tasks such as object detection, image recognition and data compression. However, current corner detection algorithms are complex and time consuming. In this paper, a new quantum fast corner detection algorithm is proposed taking full advantage of quantum parallelism. The algorithm is implemented in three steps: the 'nucleus' is defined and its neighborhood pixels are determined in the first step. Two thresholds are selected in the second step, and corners are obtained in the third step. The first and second steps are the same as the classical corner detection algorithm. The third step is divided into two stages. In the first stage, the differences between grayscale values of the nucleus and pixels in the neighborhood are calculated, followed by the comparison of those differences with the 'intensity threshold,' then is the quantum measurement on the comparison results, and finally the measured results are organized into an array. In the second stage, the array is used for counting, followed by the comparison of those counted results with the 'accuracy threshold,' and finally the corners are obtained. It is worth noting that through the quantum–classical–quantum mode, quantum resources can be reduced significantly. The analysis in the proposed quantum fast corner detection algorithm shows that the time complexity and quantum delay of the algorithm do not increase with the increase in the size and number of images, and its time complexity is exponentially lower than that of the classical fast corner detection algorithm. [ABSTRACT FROM AUTHOR]

In the previous research on solving the elliptic curve discrete logarithm problem, quantum resources were concretely estimated. In Banegas et al. (IACR Trans Cryptogr Hardw Embed Syst 2021(1):451–472, 2020. https://doi.org/10.46586/tches.v2021.i1.451-472), the quantum algorithm was optimized for binary elliptic curves, with the main optimization target being the number of the logical qubits. The division algorithm was primarily optimized in Banegas et al. (2020) since every ancillary qubit is used in the division algorithm. In this paper, we propose a new quantum division algorithm on the binary field that uses fewer qubits. Specifically, for elements in a field of 2 n , our algorithm saves n - 3 ⌊ log n ⌋ - 2 qubits instead of using n 2 - 64 n ⌊ log (n) ⌋ + O (n) more Toffoli gates, which leads to a more space-efficient quantum algorithm for binary elliptic curves. For the small size n of 16, 127, 163, 233, 283 and 571, both the number of qubits and the number of Toffoli gates are actually reduced. When the size n is 571, the reduction in ancillary qubits amounts to approximately 23% compared to the previous algorithm. [ABSTRACT FROM AUTHOR]

Privacy amplification (PA) is an essential part in a quantum key distribution (QKD) system, distilling a highly secure key from a partially secure string by public negotiation between two parties. The optimization objectives of privacy amplification for QKD are large block size, high throughput and low cost. For the global optimization of these objectives, a novel privacy amplification algorithm is proposed in this paper by combining multilinear-modular-hashing and modular arithmetic hashing. This paper proves the security of this hybrid hashing PA algorithm within the framework of both information theory and composition security theory. A scheme based on this algorithm is implemented and evaluated on a CPU platform. The results on a typical CV-QKD system indicate that the throughput of this scheme ( 261 Mbps @ 2.6 × 10 8 input block size) is twice higher than the best existing scheme ( 140 Mbps @ 1 × 10 8 input block size). Moreover, this scheme is implemented on a mobile CPU platform instead of a desktop CPU or a server CPU, which means that this algorithm has a better performance with a much lower cost and power consumption. [ABSTRACT FROM AUTHOR]

The solution of linear systems of equations is a very frequent operation and thus important in many fields. The complexity using classical methods increases linearly with the size of equations. The HHL algorithm proposed by Harrow et al. achieves exponential acceleration compared with the best classical algorithm. However, it has a relatively high demand for qubit resources, and the solution x is in a normalized form. Assuming that the eigenvalues of the coefficient matrix of the linear systems of equations can be represented perfectly by finite binary number strings, the hybrid iterative phase estimation algorithm (HIPEA) is designed based on the iterative phase estimation algorithm in this paper. The complexity is transferred to the measurement operation in an iterative way, and thus, the demand of qubit resources is reduced in our hybrid algorithm. Moreover, the solution is stored in a classical register instead of a quantum register, so the exact unnormalized solution can be obtained. The required qubit resources in the three variants of HIPEA are different. The first variant only needs one single ancillary qubit. The number of ancillary qubits in the second variant is equal to the number of nondegenerate eigenvalues of the coefficient matrix of linear systems of equations. The third variant is designed with a flexible number of ancillary qubits. The HIPEA algorithm proposed in this paper broadens the application range of quantum computation in solving linear systems of equations by avoiding the problem that quantum programs may not be used to solve linear systems of equations due to the lack of qubit resources. [ABSTRACT FROM AUTHOR]

At SAC 2021, Frixons et al. proposed quantum boomerang attacks that can effectively recover the keys of block ciphers in the quantum setting. Based on their work, we further consider how to quantize the generic boomerang attacks proposed by Biham et al. at FSE 2002, so as to obtain more generic quantum boomerang attacks. Similar to Frixons et al.'s work, we only consider quantum key recovery attacks in the single-key setting. With the help of some famous quantum algorithms, this paper presents two methods to convert the attacks of Biham et al. into some new quantum key recovery attacks. In order to proof our methods, we apply our new ideas to attack Serpent-256 and ARIA-196. To sum up, for Serpent-256, we give valid 9-round and 10-round quantum key recovery attacks respectively. The quantum time complexity of 9-round and 10-round of Serpent-256 is 2 115.43 and 2 126.6 respectively. Furthermore, we show a valid quantum key attack on 6-round ARIA-196 which has a time complexity of 2 89.8 with negligible memory. The time complexity of the above quantum attacks are better than the corresponding classical attacks and quantum generic key recovery attack via Grover's algorithm. [ABSTRACT FROM AUTHOR]

Because of the low accuracy in intrusion detection, a model of extreme learning machine based on the optimization of quantum beetle swarm algorithm is proposed. First of all, this paper proposes a quantum beetle swarm optimization algorithm, which introduces quantum mechanics and combines the advantages of beetle antennae search and particle swarm optimization. In this way, the individual can learn both their own experience and group experience, which enables the beetle to move purposefully and instructively, and improves the convergence performance of the algorithm. In extreme learning machine, it is more difficult to solve the problem in high-dimensional data. This paper proposed an improved extreme learning machine that uses the least squares QR algorithm to decompose the matrix, which can reduce the computational complexity of the traditional extreme learning machine. The improved extreme learning machine model optimized by quantum beetle swarm optimization algorithm is applied to intrusion detection, and the simulation results show that the model proposed in this paper can significantly improve detection accuracy and increase convergence rate. [ABSTRACT FROM AUTHOR]

Monte Carlo integration using quantum computers has been widely investigated, including applications to concrete problems. It is known that quantum algorithms based on quantum amplitude estimation (QAE) can compute an integral with a smaller number of iterative calls of the quantum circuit which calculates the integrand, than classical methods call the integrand subroutine. However, the issues about the iterative operations in the integrand circuit have not been discussed so much. That is, in the high-dimensional integration, many random numbers are used for calculation of the integrand and in some cases similar calculations are repeated to obtain one sample value of the integrand. In this paper, we point out that we can reduce the number of such repeated operations by a combination of the nested QAE and the use of pseudorandom numbers (PRNs), if the integrand has the separable form with respect to contributions from distinct random numbers. The use of PRNs, which the authors originally proposed in the context of the quantum algorithm for Monte Carlo, is the key factor also in this paper, since it enables parallel computation of the separable terms in the integrand. Furthermore, we pick up one use case of this method in finance, the credit portfolio risk measurement and estimate to what extent the complexity is reduced. [ABSTRACT FROM AUTHOR]

The quantum image segmentation algorithm is to divide a quantum image into several parts, but most of the existing algorithms use more quantum resource(qubit) or cannot process the complex image. In this paper, an improved two-threshold quantum segmentation algorithm for NEQR image is proposed, which can segment the complex gray-scale image into a clear ternary image by using fewer qubits and can be scaled to use n thresholds for n + 1 segmentations. In addition, a feasible quantum comparator is designed to distinguish the gray-scale values with two thresholds, and then a scalable quantum circuit is designed to segment the NEQR image. For a 2 n × 2 n image with q gray-scale levels, the quantum cost of our algorithm can be reduced to 60 q - 6 , which is lower than other existing quantum algorithms and does not increase with the image's size increases. The experiment on IBM Q demonstrates that our algorithm can effectively segment the image. [ABSTRACT FROM AUTHOR]

In this paper, we introduce and study the quantum measurement detection algorithms (QMDA), whose objective is to detect whether unwanted measurements are being taken in a quantum circuit or not by applying the Zeno effect. A QMDA is a quantum circuit that includes three unitary matrices, one of them being applied numerous times consecutively, and whose initial state is fixed when no foreign measurements occur. One example is the Elitzur–Vaidman bomb tester, which is generalized by the QMDA definition, allowing the detection of measurements that are taken in an unknown basis and in circuits with an arbitrary number of qubits. We prove some key properties and limitations of these algorithms, as well as studying the performance of the Elitzur–Vaidman bomb tester and its possible improvements. Some extensions of the definition would lead to algorithms such as the counterfactual communication one. [ABSTRACT FROM AUTHOR]

Various quantum computing simulation platforms have developed rapidly in the last 3 years. However, few quantum image processing algorithms are simulated in these platforms. In this paper, we design a dual-threshold quantum image segmentation algorithm and simulate it in IBM Q Experience platform through Qiskit extension. The NEQR quantum image representation model is firstly optimized and simulated, which is found that the number of the auxiliary qubits will not increase as the image's size increases. Then, an efficient quantum comparator to realize the comparison of two numbers is designed. And finally, the high parallelism image segmentation algorithm is proposed and simulated. Suppose the size of an image is 2 n × 2 n and the gray-scale scope is [0, 2 q - 1 ], the time complexity analysis for the quantum image segmentation algorithm shows that the number of basic quantum gate required is proportional to q and will not increase as image's size increases. Thus, the proposed quantum segmentation algorithm is highly parallelism and has polynomial time complexity. In addition, the simulation part of this paper will provide reference for other quantum image processing algorithms. [ABSTRACT FROM AUTHOR]

The arithmetic of finite fields with characteristic 2 is central in many cryptographic algorithms. Based on the normal basis representation for elements of the finite field F 2 n , quantum circuits for addition and multiplication have complexities O(n) and O (n 3) , respectively. However, the complexity of the quantum circuit performing multiplication in F 2 n can be reduced to O (n 2) provided that F 2 n contains an optimal normal basis. In this paper, a lossless quantum circuit for the affine transforms on F 2 n is designed with the quadratic time complexity for some values of n. Moreover, each constituent of the affine transforms on F 2 n is a unitary operation, and accordingly, the domain of these transforms can be extended to the 2 n -dimensional Hilbert space H ⊗ n . In addition, these transforms are one–one mappings from the set of computational basis states, of H ⊗ n , to itself. This property of affine transforms confirms that these transforms can be used in the encryption algorithms for quantum images because a quantum image uses the computational basis states for storing the color and positional information of pixels. Accordingly, a fast quantum image encryption algorithm combining affine transforms with fractional-order Lorenz-like system is presented for the novel quantum representation of color digital images. A selected pair of affine transforms is used to scramble the position information of the quantum image, while the color information of red, blue, and green layers of the scrambled quantum image is encrypted through controlled right translations determined by the fractional-order Lorenz-like system. Analyses of the time complexity reveal that the proposed quantum image scrambling scheme is exponentially faster than some state-of-the-art schemes. Simulation results confirm that the newly suggested encryption algorithm is fast, robust, and reliable. [ABSTRACT FROM AUTHOR]

In this paper, we propose a quantum algorithm to efficiently perform locality preserving projection (LPP) for dimensionality reduction, named quantum locality preserving projection (QLPP). We present QLPP in 4 steps and give their corresponding quantum circuits. Furthermore, we give an improved algorithm to construct the density matrix proportional to the Hermitian/non-Hermitian chain product composed of multiple Hermitian/non-Hermitian matrices in QLPP. The analysis results show that the computation complexity of QLLP is O (d κ eff 10 m polylog (m) / ε 7) for m ≫ n , where κ eff is a predefined condition number, m is the number of training data with dimension n, d is the dimension of reduced dimension feature space, and ε denotes the tolerance error. It is polynomial speedup in m compared to classical LPP algorithm, whose complexity is O (m 2 n) . [ABSTRACT FROM AUTHOR]

Due to the fact that many classical numerical methods have not yet mature quantum counterparts, quantum circuit design is very important in quantum image processing. In this paper, using the novel enhanced quantum representation (NEQR) model, an image encryption algorithm based on Feistel structure is carried out in quantum computer by giving the encryption quantum circuits. First, the modified Feistel structure for image encryption is proposed. It is a 128-bit block cipher and requires 16-bit subkeys to encrypt the image, and it is a mixture of Feistel and substitution–permutation network; then, the detailed quantum circuits design of the encryption algorithm are given. Through numerical simulation and analysis, it is verified that the proposed quantum image encryption algorithm is effective and can resist statistical attacks effectively. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel quantum algorithm, based on the Bernstein–Vazirani algorithm, for finding a if the function f x = a · π x , where a , x ∈ 0 , 1 2 and π x is a 2-bit permutation function. Note that the Bernstein–Vazirani algorithm cannot find a when we select the function f x = a · π x , where π x = 0 1 2 3 2 0 1 3 . Our algorithm can be further applied to Nagata et al.'s problem. Our algorithm will output g A 1 and g A 0 if the function f x = g A 1 g A 0 2 · π x , where A 1 , A 0 ∈ 0 , 1 m , x ∈ 0 , 1 2 and g : 0 , 1 m → 0 , 1. [ABSTRACT FROM AUTHOR]

HHL algorithm is a quantum algorithm for solving linear equation system. It can achieve an exponential improvement over the best classical algorithm. In this paper, we analyze the quantum security of Grain-128/Grain-128a stream cipher by using the HHL algorithm. Our algorithm is based on Chen and Gao's research on solving nonlinear equation system in Chen et al. (Quantum algorithm for optimization and polynomial system solving over finite field and application to cryptanalysis, 2018. arXiv:1802.03856) and Chen et al. (Quantum algorithms for Boolean equation solving and quantum algebraic attack on cryptosystems, 2017. arXiv:1712.06239). Firstly, we build a nonlinear Boolean equation system by choosing any keystream. Then, the nonlinear equation system is transformed into a special linear equation system that can be solved with the HHL algorithm. Finally, we solve the system by the HHL quantum algorithm. Our attack requires N > 2 8 -bit keystream, and the complexity is O (2 21 N 3.5 κ 2 e ϵ / ϵ 0.5) for Grain-128, and O (2 21.5 N 3.5 κ 2 e ϵ / ϵ 0.5) for Grain-128a where κ is the condition number of the matrix of the corresponding linear systems and ϵ is a given error bound. Then we give a toy example of Grain family to estimate κ and briefly analyze the security of Grain-128/Grain-128a against HHL algorithm. [ABSTRACT FROM AUTHOR]

The development of quantum computers has urged the cryptographic community to prepare cryptographic primitives for the eventual arrival of the post-quantum world. At Asiacrypt 2017, Leander and May combined Grover's and Simon's quantum algorithms to break the FX-based block ciphers. Technically this result is based on the combination of the quantum algorithms of Grover's and Simon's for the first time in the cryptographic setting. In this study, we using Bernstein–Vazirani's and Grover's algorithms to generate a new quantum key-recovery attacks on different rounds of Feistel constructions. An advantage of our attack is the keys can be divided into multiple blocks to enter the S-box and realize the process of recovery; this method greatly reduces the complexity of key recovery. Hence, it has strong practicability for key recovery (e.g., DES, Camellia, etc.). In order to show that, a detailed process has been provided in this paper. [ABSTRACT FROM AUTHOR]

The quantum state discrimination problem is to distinguish between non-orthogonal quantum states. This problem has many applications in quantum information theory, quantum communication and quantum cryptography. In this paper, a quantum algorithm using weak measurement and partial negation will be proposed to solve the quantum state discrimination problem using a single copy of an unknown qubit. The usage of weak measurement makes it possible to reconstruct the qubit after measurement since the superposition will not be destroyed due to measurement. The proposed algorithm will be able to determine, with high probability of success, the state of the unknown qubit and whether it is encoded in the Hadamard or the computational basis by counting the outcome of the successive measurements on an auxiliary qubit. [ABSTRACT FROM AUTHOR]

Quantum key distribution (QKD) provides information-theoretic security based on the laws of quantum mechanics. The construction of QKD network (QKDN) is an important foundation for the widely use of quantum keys (QKs). Considering the link status flooding and unreasonable link costing of the existing researches, we propose a new routing scheme for QKDN based on application demand adaptation, named ADA-QKDN in this paper. Firstly, the routing management center is set up based on the idea of software defined network, which is used to collect the network topology information and complete the path selection, so as to reduce the data processing pressure of quantum nodes. Then, the application demand is taken as an important factor in the routing strategy. Meanwhile, the link evaluation indicators are dynamically adjusted, which is designed to provide optimal paths for applications and maximize the utilization efficiency of link resources. Finally, the impact of path hops is considered comprehensively to minimize the wastage of QKs. The simulation results show that compared with those existing schemes, the proposed ADA-QKDN increases the request success rate by more than 10%, while the effective key rate is similar to the routing schemes based on shortest path first algorithm. [ABSTRACT FROM AUTHOR]

Emerging quantum technologies represent a promising alternative for solving hard combinatorial problems in the post-Moore's law era. For practical purposes, however, the current number of qubits limits the direct applicability to larger real-world instances in the near-term future. Therefore, a promising strategy to overcome this issue is represented by hybrid quantum classical algorithms which leverage classical as well as quantum devices. One prominent example of a hard computational problem is the community detection problem: a partition of a graph into distinct communities such that the ratio between intra-community and inter-community connectivity is maximized. In this paper, we explore the current potential of quantum annealing and gate-based quantum technologies to solve the community detection problem for an arbitrary number of communities. For this purpose, existing algorithms are (re-)implemented and new hybrid algorithms, that can be run on gate-model devices, are proposed. Their performance on standardized benchmark graphs has been evaluated and compared to the one of a state-of-the-art classical heuristic algorithm. Although no quantum speed-up has been achieved, the existing quantum annealing-based methods as well as the novel hybrid algorithms for gate-based quantum computers yield modularity values, which are similar to those of the classical heuristic. However, the modular architecture of the used algorithms allows for fast utilization of more powerful quantum technologies once they become available. Reproducibility: Our code and data are publicly available (Github in Quantum Modularization. https://github.com/jku-win se/quantum_modularization 2021). [ABSTRACT FROM AUTHOR]

Quantum computing is a field of study aimed at developing technologies based on the principles of quantum theory. In this research area, enormous theoretical progress has been made, but at the current state, few quantum algorithms have been developed. It is very hard to efficiently construct new ones. The complexity is due to the non-intuitive nature of quantum operations. To overcome this obstacle, we opt for the integration of an automatic design approach. In this paper, we propose an adapted version of BackTracking algorithm allowing complete but optimal exploration of the quantum circuits space. For a given problem, the test of possible quantum gate sequences is optimized by using a constraint making it possible to ignore all unnecessary calculation in an efficient manner. In addition, solutions are generated automatically without resorting to mathematical formulas. Our approach allowed us to generate two new versions of controlled quantum teleportation. In the first version, the controller can switch the teleported Qubit between two possible distant receivers, while in the second version, this controller can choose between two different transmitters. [ABSTRACT FROM AUTHOR]

In this paper, we propose a quantum algorithm for recommendation systems which incorporates the contextual information of users to the personalized recommendation. The preference information of users is encoded in a third-order tensor of dimension N which can be approximated by the truncated tensor singular value decomposition (t-svd) of the subsample tensor. Unlike the classical algorithm that reconstructs the approximated preference tensor using truncated t-svd, our quantum algorithm obtains the recommended product under certain context by measuring the output quantum state corresponding to an approximation of a user's dynamic preferences. The algorithm achieves the time complexity O (k N polylog (N)) , compared to the classical counterpart with complexity O (k N 3) , where k is the truncated tubal rank. [ABSTRACT FROM AUTHOR]

Simon's algorithm is a well-known quantum algorithm which can achieve an exponential acceleration over classical algorithm. It has been widely used in quantum cryptanalysis of many cryptographic primitives. This paper concentrates on studying the applications of Simon's algorithm in analyzing the security of Feistel variants, several well-known cryptographic structures derived from the Feistel structure. First, we propose a definition of weakly periodic function to relax the original strong Simon's promise. Based on this definition, we define and analyze several extensions of Simon's problem which expand the application of Simon's algorithm. Furthermore, based on one extended Simon's problem, we show new polynomial-time quantum distinguishing attacks on several Feistel variants: MISTY L/R, CAST256-like, CLEFIA-like, MARS-like, SMS4-like and Skipjack-A/B-like schemes. These new results show that classically secure schemes may be no longer secure in the Q2 model. Finally, based on the quantum distinguishers introduced above, we extend several rounds forward or backward to propose corresponding quantum all subkeys recovery attacks that can recover all subkeys in the Q2 model with lower query complexities than those in the Q1 model by using Grover's algorithm. [ABSTRACT FROM AUTHOR]

This paper proposes an efficiency quantum image steganography protocol based on improved exploiting modification direction algorithm (QIS-IEMD). The new methods of expanding modification range and dynamically sharing between subgroups are introduced in the new protocol. Compared with the quantum image steganography protocol based on EMD algorithm (QIS-EMD), secret information can be embedded on multiple bit planes after expanding pixel's modification range, and the carrier pixel groups can be dynamically shared to achieve higher embedding efficiency, embedding rate and larger capacity. In addition, in order to reflect the feasibility and practicability of QIS-IEMD, dedicated quantum circuits for embedding and extracting secret information are designed for it. Finally, the experimental results and detailed mathematical analysis prove that, compared with QIS-EMD, QIS-IEMD not only performs well in imperceptibility, but also significantly increases embedding efficiency, embedding rate and capacity. [ABSTRACT FROM AUTHOR]

The Goldreich–Levin algorithm was originally proposed for a cryptographic purpose and then applied to learning. The algorithm is to find some larger Walsh coefficients of an n variable Boolean function. Roughly speaking, it takes a p o l y (n , 1 ϵ log 1 δ) time to output the vectors w with Walsh coefficients S (w) ≥ ϵ with probability at least 1 - δ . However, in this paper, a quantum algorithm for this problem is given with query complexity O (log 1 δ ϵ 4) , which is independent of n. Furthermore, the quantum algorithm is generalized to apply for an n variable m output Boolean function F with query complexity O (2 m log 1 δ ϵ 4) . [ABSTRACT FROM AUTHOR]

In this paper, we propose a quantum algorithm for approximating the QR decomposition of any N × N matrix with a running time O (1 ϵ 2 N 2.5 polylog (N)) , where ϵ is the desired precision. This quantum algorithm provides a polynomial speedup over the best classical algorithm, which has a running time O (N 3) . Our quantum algorithm utilizes the quantum computation in the computational basis (QCCB) and a setting of updatable quantum memory. We further present a systematic approach to applying the QCCB to simulate any quantum algorithm. By this approach, the simulation time does not exceed O (N 2 polylog (N)) times the running time of the quantum algorithm originally designed with the amplitude encoding method, where N is the size of the problem. [ABSTRACT FROM AUTHOR]

Quantum algorithms for the analysis of Boolean functions have received a lot of attention over the last few years. The algebraic normal form (ANF) of a linear Boolean function can be recovered by using the Bernstein–Vazirani (BV) algorithm. No research has been carried out on quantum algorithms for learning the ANF of general Boolean functions. In this paper, quantum algorithms for learning the ANF of quadratic Boolean functions are studied. We draw a conclusion about the influences of variables on quadratic functions, so that the BV algorithm can be run on them. We study the functions obtained by inversion and zero-setting of some variables in the quadratic function and show the construction of their quantum oracle. We introduce the concept of "club" to group variables that appear in quadratic terms and study the properties of clubs. Furthermore, we propose a bunch of algorithms for learning the full ANF of quadratic Boolean functions. The most efficient algorithm, among those we propose, provides an O(n) speedup over the classical one, and the number of queries is independent of the degenerate variables. [ABSTRACT FROM AUTHOR]

In this paper, we propose an improved quantum algorithm for the minimum mean square error-based massive multiple-input multiple-output (MIMO) uplink. The new algorithm can reduce the dependency on the assumptions on the input vector, the channel matrix entries and the low rank of the channel matrix, which are indispensable in our previous results. Our improved quantum algorithm applies the quantum block-encoding technology, which depends on the quantum-accessible data structure. Moreover, we design an efficient algorithm for outputting classical data, which makes sure that output data can be utilized in classical devices. Both theoretically mathematical analyses and simulation realizations in massive MIMO systems confirm the applicability of the improved quantum algorithm. With desired precision, and theoretical and numerical analysis, our improved quantum algorithm can achieve a quadratic or even an exponential speedup over classical counterparts. [ABSTRACT FROM AUTHOR]

Although Durr and Hoyer have proposed state-of-the-art quantum algorithm (DHA) for searching minimum value, the lower limit of DHA's successful probability is 1/2. Also, DHA requires approximately (log 2 N) 2 copies of the initial state. In this paper, we propose a new quantum maximum or minimum searching algorithm (QUMMSA). In big data scenarios, according to sparse sampling with different densities, we can estimate the corresponding precision parameters. QUMMSA can improve the successful probability close to 100 % . Furthermore, with the quantum exact search algorithm, QUMMSA only requires approximately log 2 N copies of the initial state to solve this problem. Since preparing an arbitrary quantum state is a problem with exponential complexity, our algorithm has a greater advantage with the increasing database size. In addition, we first propose a general method for circuits construction, which can be used in any database. An experiment implemented in an IBM superconducting processor and a numerical simulation of a 6-qubit system to solve a real issue indicate the feasibility and efficiency of QUMMSA. QUMMSA can serve as a subroutine in various quantum algorithms which involves searching maximum or minimum. [ABSTRACT FROM AUTHOR]

In this paper, we study Quantum Abstract Detecting Systems (QADS), that generalize some key characteristics of the operators used in Grover's algorithm, a wide variety of quantum walks and the quantum abstract search algorithm. A QADS is an algorithm that constructs a quantum state and a quantum operator that help testing whether a circuit-implemented boolean function f is identically zero. We also identify some relatively weak properties of QADS that lead to the construction of algorithms for the detection problem (i.e. determining whether there is a marked element in a given set). Our results provide not only a common framework to all the aforementioned search methods, and their transformation into algorithms for the detection problem, but also allow the development of new similar methods. As an example, we construct a modification of Grover's algorithm (from the tensor product of controlled QADS) that shows improved detection probability. [ABSTRACT FROM AUTHOR]

Due to the powerful computing capability of quantum computers, cryptographic researchers have applied quantum algorithms to cryptanalysis and obtained many interesting results in recent years. In this paper, we study related-key attack in the quantum setting and propose a specific related-key attack, which can recover the key of block ciphers efficiently as long as the attacked block ciphers satisfy certain condition. The attack algorithm employs the Bernstein–Vazirani algorithm as a subroutine and requires the attacker to query the encryption oracle with quantum superpositions. We give a condition under which the attack will succeed and prove that any block cipher either satisfies the condition or has a distinguishing attack. As a specific example of its application, we use the attack algorithm to extract the private key of the Even–Mansour cipher. The results of this study show the power of related-key attack when combined with quantum algorithms and provide guidance for the design of quantum-secure block ciphers. [ABSTRACT FROM AUTHOR]

Quantum cryptography improves efficiency and security of image content protection owing to the characteristics of qubits. In this paper, a novel quantum image encryption algorithm based on bit-plane permutation and sine logistic map is presented. The image to be encrypted is firstly represented with novel enhanced quantum representation model and then the quantum Arnold transform is used to scramble pixel positions. The bit-plane cross-exclusive OR and shift operations are designed to change the pixel values. The final ciphertext image is obtained through a diffusion process utilizing sine logistic map, which extremely enlarges key space. The quantum circuits of each procedure are given. Simulation results and theoretical analysis verify that the proposed quantum image scheme has good performance in the aspect of security and the computational complexity is superior to its classical counterpart. [ABSTRACT FROM AUTHOR]

The universal blind quantum computation (UBQC) is a scheme to allow a client to delegate a computation to a remote server while concealing the input, output and algorithm. However, the qubit errors are inevitable in the practical application. In this paper, a fault-tolerant quantum error correction code preparation protocol with weak coherent pulses is proposed for fault-tolerant UBQC. Furthermore, the ϵ -correctness and ϵ -blindness of the protocol are fully proven. The simulation results show that the required number of pulses in our protocol is much less than that of the remote blind qubit state preparation protocol with two decoy states in case of the same probability of successful preparation, and is closer to asymptotic case. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel quantum learning algorithm, based on Younes' quantum circuit, to find dependent variables of the Boolean function f : 0 , 1 n → 0 , 1 with one uncomplemented product of two variables. Typically, in the worst-case scenario, two dependent variables are found by evaluating the function O n times. However, our proposed quantum algorithm only requires O log 2 n function operations in the worst-case. Additionally, we evaluate the average number to perform the function. In the average case, our algorithm requires O 1 function operations. [ABSTRACT FROM AUTHOR]

In typical well-known cryptosystem, the hardness of classical problems plays a fundamental role in ensuring its security. While, with the booming of quantum computation, some classical hard problems tend to be vulnerable when confronted with the already-known quantum attacks, as a result, it is necessary to develop the post-quantum cryptosystem to resist the quantum attacks. With the purpose to bridge the two disciplines, it is significant to summarize known quantum algorithms and their threats toward these cryptographic intractable problems from a perspective of cryptanalysis. In this paper, we discussed the designing methodology, algorithm framework and latest progress of the mathematic hard problems on which the typical cryptosystems depend, including integer factorization problem, discrete logarithmic problem and its variants, lattice problem, dihedral hidden subgroup problems and extrapolated dihedral coset problem. It illustrated the reason why some cryptosystems such as RSA and ECC are not resistant to quantum attacks, yet some of them like lattice cryptosystems remain intact facing quantum attacks. [ABSTRACT FROM AUTHOR]