Complexity theory Archives - IEEE Transactions on Quantum Engineering

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

Relation Between Quantum Advantage in Supervised Learning and Quantum Computational Advantage

December 26, 2023Jordi Pérez-GuijarroQuantum ComputingComplexity theory, Cost function, Machine learning, Quantum algorithm, Supervised learning, Task analysis, Training

Quantum Algorithm for Position Weight Matrix Matching

August 18, 2023Koichi MiyamotoQuantum ComputingBioinformatics, Biology, Complexity theory, DNA, Proteins, Pulse width modulation, Quantum algorithm

In this article, we propose two quantum algorithms for a problem in bioinformatics, position weight matrix (PWM) matching, which aims to find segments (sequence motifs) in a biological sequence, such as DNA and protein that have high scores defined by the PWM and are, thus, of informational importance related to biological function. The two proposed […]