Approximation algorithms Archives - IEEE Transactions on Quantum Engineering

Benchmarking Quantum Circuit Transformation With QKNOB Circuits

January 8, 2025Sanjiang Li, Xiangzhen Zhou, Yuan FengQuantum SoftwareApproximation algorithms, Benchmark testing, Costs, Logic gates, Performance evaluation, Quantum circuit, Quantum mechanics, Qubit, Scalability, Transforms

Current superconducting quantum devices impose strict connectivity constraints on quantum circuit execution, necessitating circuit transformation before executing quantum circuits on physical hardware. Numerous quantum circuit transformation (QCT) algorithms have been proposed. To enable faithful evaluation of state-of-the-art QCT algorithms, this article introduces qubit mapping benchmark with known near-optimality (QKNOB), a novel benchmark construction method for […]

Noise Robustness of Quantum Relaxation for Combinatorial Optimization

August 6, 2024Kentaro Tamura, Yohichi Suzuki, Rudy Raymond, Hiroshi C. Watanabe, Yuki Sato, Ruho Kondo, Michihiko Sugawara, Naoki YamamotoQuantum ComputingApproximation algorithms, Decoding, Encoding, Noise, Optimization, Quantum state, Qubit

Relaxation is a common way for dealing with combinatorial optimization problems. Quantum random-access optimization (QRAO) is a quantum-relaxation-based optimizer that uses fewer qubits than the number of bits in the original problem by encoding multiple variables per qubit using quantum random-access code (QRAC). Reducing the number of qubits will alleviate physical noise (typically, decoherence), and […]

Noise Robustness of Quantum Relaxation for Combinatorial Optimization

August 6, 2024Kentaro Tamura, Yohichi Suzuki, Rudy Raymond, Hiroshi C. Watanabe, Yuki Sato, Ruho Kondo, Michihiko Sugawara, Naoki YamamotoQuantum Computer ArchitectureApproximation algorithms, Decoding, Encoding, Noise, Optimization, Quantum state, Qubit

Relaxation is a common way for dealing with combinatorial optimization problems.

Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture

May 8, 2024Carlo Mastroianni, Francesco Plastina, Jacopo Settino, Andrea Vinci,Quantum ComputingApproximation algorithms, Cloud computing, Heuristic algorithms, Optimization, Quantum algorithm, Quantum computing, Task analysis

Modern cloud/edge architectures need to orchestrate multiple layers of heterogeneous computing nodes, including pervasive sensors/actuators, distributed edge/fog nodes, centralized data centers, and quantum devices. The optimal assignment and scheduling of computation on the different nodes is a very difficult problem, with NP-hard complexity. In this article, we explore the possibility of solving this problem with […]

Multiobjective Optimization and Network Routing With Near-Term Quantum Computers

April 16, 2024Shao-Hen Chiew, Kilian Poirier, Rajesh Mishra, Ulrike Bornheimer, Ewan Munro, Si Han Foon, Christopher Wanru Chen, Wei Sheng Lim, Chee Wei NgaQuantum ComputingApproximation algorithms, Computers, Numerical simulation, Optimization, Quantum computing, Routing, Shortest path problem

Multiobjective optimization is a ubiquitous problem that arises naturally in many scientific and industrial areas. Network routing optimization with multiobjective performance demands falls into this problem class, and finding good quality solutions at large scales is generally challenging. In this work, we develop a scheme with which near-term quantum computers can be applied to solve […]

Quantum Approximate Bayesian Optimization Algorithms With Two Mixers and Uncertainty Quantification

October 25, 2023Jungin E. KimQuantum ComputingApproximation algorithms, Mixers, Optimization, Quantum circuit, Quantum computing, Qubit, Uncertainty

The searching efficiency of the quantum approximate optimization algorithm is dependent on both the classical and quantum sides of the algorithm. Recently, a quantum approximate Bayesian optimization algorithm (QABOA) that includes two mixers was developed, where surrogate-based Bayesian optimization is applied to improve the sampling efficiency of the classical optimizer. A continuous-time quantum walk mixer […]

Bayesian Optimization for QAOA

October 16, 2023Simone TibaldiRegularApproximation algorithms, Bayes methods, Optimization, Quantum circuit, Qubit, Task analysis, Training

The quantum approximate optimization algorithm (QAOA) adopts a hybrid quantum-classical approach to find approximate solutions to variational optimization problems. In fact, it relies on a classical subroutine to optimize the parameters of a quantum circuit. In this article, we present a Bayesian optimization procedure to fulfill this optimization task, and we investigate its performance in […]

Shor’s Algorithm Using Efficient Approximate Quantum Fourier Transform

September 25, 2023Kento OonishiQuantum ComputingApproximation algorithms, Computational efficiency, Fault tolerance, Fault tolerant systems, Fourier transforms, Logic gates, Qubit

Shor’s algorithm solves the integer factoring and discrete logarithm problems in polynomial time. Therefore, the evaluation of Shor’s algorithm is essential for evaluating the security of currently used public-key cryptosystems because the integer factoring and discrete logarithm problems are crucial for the security of these cryptosystems. In this article, a new approximate quantum Fourier transform […]

Analysis of the Vehicle Routing Problem Solved via Hybrid Quantum Algorithms in the Presence of Noisy Channels

August 10, 2023Nishikanta MohantyQuantum ComputingApproximation algorithms, Mathematical models, Minimization, Optimization, Quantum computing, Software, Stationary state

The vehicle routing problem (VRP) is an NP-hard optimization problem that has been an interest of research for decades in science and industry. The objective is to plan routes of vehicles to deliver goods to a fixed number of customers with optimal efficiency. Classical tools and methods provide good approximations to reach the optimal global […]

Efficient Quantum State Preparation for the Cauchy Distribution Based on Piecewise Arithmetic

November 2, 2022Ethan T. WangOpen Access, Quantum ComputingApproximation algorithms, Distribution functions, Logic gates, Mathematical models, Monte Carlo methods, Qubit, Registers

The benefits of the quantum Monte Carlo algorithm heavily rely on the efficiency of the superposition state preparation. So far, most reported Monte Carlo algorithms use the Grover–Rudolph state preparation method, which is suitable for efficiently integrable distribution functions. Consequently, most reported works are based on log-concave distributions, such as normal distributions. However, non-log-concave distributions […]