Quantum algorithm complexity

Daowen Qiu

Xiang-Qun Fu, Wan‐Su Bao, Xiang 翔 Wang 汪 +1 more

Abstract Similar to the classical meet-in-the-middle algorithm, the storage and computation complexity are the key factors that decide the efficiency of the quantum meet-in-the-middle algorithm. Aiming at the target vector of fixed weight, based on the quantum meet-in-the-middle algorithm, the algorithm for searching all n-product vectors with the same weight is presented, whose complexity is better than the exhaustive search algorithm. And the algorithm can reduce the storage complexity of the quantum meet-in-the-middle search algorithm. Then based on the algorithm and the knapsack vector of the Chor-Rivest public-key crypto of fixed weight d, we present a general quantum meet-in-the-middle search algorithm based on the target solution of fixed weight, whose computational complexity is ∑ j = 0 d ( O ( C n - k + 1 d - j ) + O ( C k j log C k j ) ) with Σ d i =0 C k i memory cost. And the optimal value of k is given. Compared to the quantum meet-in-the-middle search algorithm for knapsack problem and the quantum algorithm for searching a target solution of fixed weight, the computational complexity of the algorithm is lower. And its storage complexity is smaller than the quantum meet-in-the-middle-algorithm.

John Watrous

Jincheng Zhang

Quantum algorithms, renowned for their potential to solve complex problems beyond the capabilities of classical computers, often face challenges related to computational complexity. This paper introduces a novel approach to address this challenge – Adaptive Complexity Optimization of Quantum Algorithms (ACOA). We propose a method that dynamically adjusts the complexity of quantum algorithms based on the characteristics of the input data. The core mechanism centers around employing a topological quantum algorithm to decompose the algorithm's complexity into modular components, and automatically adjusting these modules based on the input's inherent structure. This adaptive approach aims to improve efficiency and scalability by effectively modeling complex data. The paper details the design of the OACO algorithm, its implementation, and preliminary experimental results demonstrating its effectiveness in tackling specific problem instances. We highlight the advantages of this method over traditional complexity optimization techniques, emphasizing its dynamic adaptability and potential for enhanced performance.

Satoshi Iriyama, Makoto Ohya

Markus Grassl, Thomas Beth

We discuss the quantum search algorithm using complex queries that has recently been published by Grover (quant-ph/9706005). We recall the algorithm adding some details showing which complex query has to be evaluated. Based on this version of the algorithm we discuss its complexity.