The discrete cosine transform (DCT) is widely used in image and video compression standard formats. This is due to its ability to represent signals and images using a limited number of significant ...coefficients without noticeable loss of visual clarity. The classical one-dimensional discrete cosine transform (1D - DCT) and two-dimensional discrete cosine transform (2D - DCT) have computational complexities of O(Nlog2N) and O(N2log2N), respectively. Thus, as the images grow in size, the runtime of the DCT highly increases which could limit its usability in real-time applications. This paper presents a quantum DCT algorithm (QDCT) that is more efficient than its classical counterpart in terms of complexity. Furthermore, the proposed QDCT is used to develop and realize a quantum image compression technique. The developed compression technique performs a search to determine the most significant computed DCT coefficients and is derived from Grover’s algorithm. It provides a generalization to the original search algorithm by utilizing two oracle operators to solve the complex unstructured search problem rather than a single one. Thus, the proposed QDCT algorithm can simultaneously calculate the DCT coefficients and identify the significant DCT coefficients through applying two oracles. The comparison of the introduced QDCT with Grover’s algorithm also indicates that the QDCT algorithm is more efficient. This can be attributed to performing a rotation on the subspace rather than on the global space in Grover’s algorithm. In addition, the presented quantum 1D - and 2D - DCT have reduced complexities compared to the classical algorithms which are O(N) and O(N), respectively. Therefore, the presented QDCT and compression algorithm can be applied efficiently to accomplish various transform-based quantum signal and image processing tasks.
•Robustness of Grover’s algorithm that uses multiphase matching.•Comparison of different phase matching modifications.•Fit by semiempirical methods (Hill fit).•Numerical simulations.•Generalized ...Householder reflection.
In this work we study five Grover’s algorithm modifications, where each iteration is constructed by two generalized Householder reflections, against inaccuracies in the phases. By using semi-empirical methods, we investigate various characteristics of the dependence between the probability to find solution and the phase errors. The first of them is the robustness of the probability to errors in the phase. The second one is how quickly the probability falls beyond the stability interval. And finally, the average success rate of the algorithm when the parameters are in the range of the highly robust interval. Two of the modifications require usage of the same Grover operator each iteration and in the other three it differs. Those semi-empirical methods give us the tool to make prediction of the quantum algorithm modifications’ overall behavior and compare them for even larger register size.
This paper exploits a quantum-empowered machine learning algorithm to enhance computation learning speed. We leverage quantum phenomena such as superposition and entanglement to work on large-scale ...multi-dimensional data represented by quantum states. Under stochastic behaviors and quantum uncertainty, we examine the offloading problem to maximize the computational task processing efficiency, considering the computation latency, energy consumption, and quantum network adaptability. From the Markov decision process, the paper proposes a novel quantum-empowered deep reinforcement learning (Qe-DRL) approach, combining quantum computing theory and machine learning to achieve exploration and exploitation trade-off via quantum parallelism significantly. Furthermore, we develop a modified Grover's algorithm with exponential convergence speed to provide a searching strategy for transition quantum states probabilities. Simulation results establish the effectiveness of the proposed Qe-DRL algorithm and its superior computational learning speed. Our proposed Qe-DRL algorithm outperforms other benchmarks in terms of energy efficiency performance.
We present a quantum probabilistic associative memory using the inverse of quantum Fourier transform and Grover’s algorithm to recover existing or similar patterns in the memory. The content of the ...memory is created using a generator of a superposition state representing a given set of patterns. We discuss the architecture of the proposed memory including the storing, recovering and processing of similarity tolerance of the input query. The associative memory can extrapolate and recover similar stored patterns. The system is unitary and runs in O(n) steps, where n is the number of qubits of the patterns.
Distributed quantum computation has gained extensive attention. In this paper, we consider a search problem that includes only one target item in the unordered database. After that, we propose a ...distributed exact Grover's algorithm (DEGA), which decomposes the original search problem into ⌊ n / 2 ⌋ parts. Specifically, (i) our algorithm is as exact as the modified version of Grover's algorithm by Long, which means the theoretical probability of finding the objective state is 100%; (ii) the actual depth of our circuit is 8 ( n mod 2 ) + 9 , which is less than the circuit depths of the original and modified Grover's algorithms, 1 + 8 ⌊ π 4 2 n ⌋ and 9 + 8 ⌊ π 4 2 n − 1 2 ⌋ , respectively. It only depends on the parity of n , and it is not deepened as n increases; (iii) we provide particular situations of the DEGA on MindQuantum (a quantum software) to demonstrate the practicality and validity of our method. Since our circuit is shallower, it will be more resistant to the depolarization channel noise.
This article presents the cost analysis of mounting Grover's key search attack on the family of KATAN block cipher. Several designs of the reversible quantum circuit of KATAN are proposed. Owing to ...the National Insitute of Standards and Technology's (NIST) proposal for postquantum cryptography standardization, the circuits are designed focusing on minimizing the overall depth. We observe that the reversible quantum circuits designed using and gates and <inline-formula><tex-math notation="LaTeX">T</tex-math></inline-formula>-depth one Toffoli gate give more shallow circuits. Grover oracle for KATAN is designed based on the reversible circuits, which are used further to mount Grover's key search attack on KATAN. The designs are implemented using the software framework ProjectQ, which provides a resource estimation tool to perform an appropriate cost analysis in an automated way. While estimating the resources, NIST's depth restrictions are also respected.
In this paper, we propose a distributed Grover's algorithm, and it requires fewer qubits and has a linear advantage in time complexity compared to the original Grover's algorithm. More exactly, to ...search for a target in an unstructured database with N elements, Grover's algorithm can get the target with query complexity O(N), but our distributed Grover's algorithm with K computing nodes can get the target with query complexity O(NK), and the number of qubits inputted in our distributed Grover's algorithm is ⌊logK⌋ less than that in Grover's algorithm. In addition, we propose an efficient algorithm of constructing quantum circuits for realizing the oracle corresponding to any Boolean function with conjunctive normal form (CNF).
•We propose a distributed Grover's algorithm with lower query times and smaller number of input bits.•We propose an efficient algorithm of constructing quantum circuits for realizing the oracle corresponding to any Boolean function with CNF.
Grover's algorithm harnesses the power of quantum computing to swiftly locate specific elements in an unstructured database, outperforming classical computers in tasks like database searching. This ...algorithm capitalizes on the unique ability of qubits to be in both 0 and 1 states simultaneously (superposition), allowing it to scan the entire search space at once. It then boosts the probability of the target element, making it more prominent. While the foundational concepts of Grover's algorithm are well-documented, practical implementation using quantum operators, especially for large search spaces, remains less explored beyond basic examples with a small number of qubits. Existing general synthesis techniques often involve numerous operators or are time-consuming. Our proposed methods specifically address the amplitude-amplification component of Grover's algorithm for any size of search space. These methods detail the required types and quantities of qubits and operators, emphasizing minimal usage and efficient assembly. Developed and evaluated in Python, our methods consistently identified target elements with over 95% accuracy and achieved configurations comparably compact as those in the existing literature but at a faster pace. We anticipate that these methods facilitate practical implementations of Grover's algorithm across various domains.
Algorithms for triangle finding, the smallest nontrivial instance of the k-clique problem, have been proposed for quantum computers. Still, those algorithms assume the use of fixed access time ...quantum RAM. In this article, we present a practical gate-based approach to both the triangle-finding problem and its NP-hard k-clique generalization. We examine both constant factors for near-term implementation on a noisy intermediate scale quantum computing (NISQ) device and the scaling of the problem to evaluate long-term use of quantum computers. We compare the time complexity and circuit practicality of the theoretical approach and actual implementation. We propose and apply two different strategies to the k-clique problem, examining the circuit size of Qiskit implementations. We analyze our implementations by simulating triangle finding with various error models, observing the effect on damping the amplitude of the correct answer, and compare to execution on six real IBM quantum machines. Finally, we estimate the approximate quantum volume needed so that the smallest instance of our approach can be executable with minimal error on a real NISQ device.
PDF
