Complexity theory Archives - IEEE Transactions on Quantum Engineering

Quantum-Assisted Optimization and Security for Trustworthy AI-Driven Healthcare

March 25, 2026Hafiz Muhammad Waseem, Gregory Epiphaniou, Carsten MapleOpen AccessAccuracy, Artificial intelligence, Complexity theory, Decision making, Electronic healthcare, Genomics, Medical services, Optimization, Scalability, Security

Abstract: Digital health increasingly relies on artificial intelligence for clinical decision-making, patient management, and distributed learning, yet two persistent challenges remain: the computational complexity of optimization tasks, such as operating-room scheduling and genomic feature selection, and the need for robust security in federated and Internet-of-Medical-Things (IoMT) systems that are vulnerable to poisoning and spoofing attacks. […]

Beyond asymptotic scaling: Comparing functional quantum linear solvers

March 16, 2026Andreea-Iulia Lefterovici, Michael Perk, Debora Ramacciotti, Antonio F. Rotundo, S. E. Skelton, Martin SteinbachOpen AccessAccuracy, Approximation algorithms, Benchmark testing, Complexity theory, Costs, Hardware, Linear systems, Mathematical models, Quantum algorithm, Standards

Abstract: Solving systems of linear equations is a key subroutine in many quantum algorithms. In the last 15 years, many quantum linear solvers (QLS) have been developed, competing to achieve the best asymptotic worst-case complexity. Most QLS assume fault-tolerant quantum computers, so they cannot yet be benchmarked on real hardware. Because an algorithm with better […]

Improved Belief Propagation Decoding Algorithms for Surface Codes

June 6, 2025Jiahan Chen; Zhengzhong Yi; Zhipeng Liang; Xuan WangUncategorizedAccuracy, Belief propagation, Codes, Complexity theory, Error correction, Maximum likelihood decoding, Noise, Qubit, Silicon, Time complexity

Abstract: Quantum error correction is crucial for universal fault-tolerant quantum computing. Highly accurate and low-time-complexity decoding algorithms play an indispensable role in ensuring quantum error correction works effectively. Among existing decoding algorithms, belief propagation (BP) is notable for its nearly linear time complexity and general applicability to stabilizer codes. However, BP’s decoding accuracy without postprocessing […]

Q-Gen: A Parameterized Quantum Circuit Generator

May 20, 2025Yikai Mao; Shaswot Shresthamali; Masaaki KondoQuantum Software, UncategorizedComplexity theory, Computational modeling, Generators, Integrated circuit modeling, Logic gates, Quantum algorithm, Quantum circuit, Quantum computing, Quantum mechanics, Qubit

Abstract: Unlike most classical algorithms that take an input and give the solution directly as an output, quantum algorithms produce a quantum circuit that works as an indirect solution to computationally hard problems. In the full quantum computing workflow, most data processing remains in the classical domain except for running the quantum circuit in the […]

Mixed Grover: A Hybrid Version to Improve Grover’s Algorithm for Unstructured Database Search

March 28, 2025Romain Piron; Muhammad Idham Habibie; Claire GoursaudQuantum ComputingApproximation algorithms, Complexity theory, Costs, Databases, Flyback transformers, Optimization, Qubit, Registers, Search problems, Signal processing algorithms

Abstract: In this article, we propose a new strategy to exploit Grover’s algorithm for unstructured search problems. We first show that running Grover’s routine with a reduced number of iterations but allowing several trials presents a complexity advantage while keeping the same success probability. Then, by a theoretical analysis of the performance, we provide a […]

Two-Dimensional Beam Selection by Multiarmed Bandit Algorithm Based on a Quantum Walk

March 26, 2025Maki Arai, Tomoki Yamagami, Takatomo Mihana, Ryoichi Horisaki, Mikio HasegawaQuantum ComputingAntenna arrays, Antenna radiation patterns, Array signal processing, Channel capacity, Complexity theory, Location awareness, Massive MIMO, Probability distribution, Quantum computing, Training

Abstract: This article proposes a novel beam selection method using a multiarmed bandit (MAB) algorithm based on a quantum walk (QW) principle, aimed at improving system performance. A massive multiple-input multiple-output system, employing multiple high-gain beams within a high-frequency band, is indispensable for achieving large capacity in future wireless communications. However, as the number of […]

Two-Step Quantum Search Algorithm for Solving Traveling Salesman Problems

March 6, 2025Rei Sato, Cui Gordon, Kazuhiro Saito, Hideyuki Kawashima, Tetsuro Nikuni, Shohei WatabeQuantum ComputingComplexity theory, Costs, Encoding, Heuristic algorithms, Optimization, Quantum algorithm, Quantum circuit, Search problems, Traveling salesman problems, Urban areas

Quantum search algorithms, such as Grover’s algorithm, are anticipated to efficiently solve constrained combinatorial optimization problems. However, applying these algorithms to the traveling salesman problem (TSP) on a quantum circuit presents a significant challenge. Existing quantum search algorithms for the TSP typically assume that an initial state—an equal superposition of all feasible solutions satisfying the […]

On Quantum Natural Policy Gradients

June 24, 2024André Sequeira, Luis Paulo Santos, Luis Soares BarbosaQuantum ComputingComplexity theory, Gradient methods, Optimization, Reinforcement learning, Stability analysis, Standards, Task analysis

This article delves into the role of the quantum Fisher information matrix (FIM) in enhancing the performance of parameterized quantum circuit (PQC)-based reinforcement learning agents. While previous studies have highlighted the effectiveness of PQC-based policies preconditioned with the quantum FIM in contextual bandits, its impact in broader reinforcement learning contexts, such as Markov decision processes, […]

Relation Between Quantum Advantage in Supervised Learning and Quantum Computational Advantage

December 26, 2023Jordi Pérez-Guijarro; Alba Pagés-Zamora; Javier R. FonollosaQuantum ComputingComplexity theory, Cost function, Machine learning, Quantum algorithm, Supervised learning, Task analysis, Training

The widespread use of machine learning has raised the question of quantum supremacy for supervised learning as compared to quantum computational advantage. In fact, a recent work shows that computational and learning advantages are, in general, not equivalent, i.e., the additional information provided by a training set can reduce the hardness of some problems. This […]

Relation Between Quantum Advantage in Supervised Learning and Quantum Computational Advantage

December 26, 2023Jordi Pérez-Guijarro, Alba Pagés-Zamora, Javier R. FonollosaQuantum ComputingComplexity theory, Cost function, Machine learning, Quantum algorithm, Supervised learning, Task analysis, Training