检索结果-内蒙古大学图书馆

quantum approximate optimization algorithm applied to multi-objective routing for large scale 6G networks

Computer Networks 2025年 267卷

作者： Bouchmal, Oumayma Cimoli, Bruno Stabile, Ripalta Vegas Olmos, Juan Jose Tafur Monroy, Idelfonso Department of Electrical Engineering Eindhoven University of Technology Eindhoven Netherlands Software Architecture NVIDIA Corporation Yokneam Israel

A multi-objective optimization problem involves optimizing two or more conflicting objectives simultaneously. This type of problem arises in many scientific and industrial areas and it is classified as NP-Hard. Network routing optimization with multiple objectives falls into this category. In the context of 6G networks, solving this problem will become even more challenging due to the exponential growth of Internet of Things devices and the high quality of service requirements. Finding good quality solutions for large-scale networks will be increasingly difficult. In this paper, we introduce a quantum-inspired routing optimization scheme in which noisy-intermediate scale quantum computers (NISQ) can be used to solve the Multi-Objective Routing Problem (MORP). We evaluate the application of the proposed scheme in detail by first developing the mathematical formulas for both single-objective and multi-objective routing and mapping the problem onto gate-based models by using the quadratic unconstrained binary optimization (QUBO) approach. To validate the proposed scheme, we use the quantum approximate optimization algorithm (QAOA), the go-to approach for solving combinatorial optimization problems that are classically intractable. For the simulation, we use the IBM-Qasm simulator and Qiskit framework. Additionally, we use the Chernoff Bound as a standard technique to estimate the sample complexity of QAOA. Finally, we provide a detailed numerical and theoretical analysis of the proposed scheme, including its time complexity, resource requirements, and the challenges associated with it. Our results demonstrate that the proposed approach operates with a time complexity of O(E2) per iteration in both single and multi-objective scenarios, with an overall runtime of (niteration + nCB) ⋅ O(E2) influenced by the sampling overhead, significantly outperforming Dijkstra's algorithm in the multi-objective case, where the complexity increases to O(2k(N(k+logN)+2kE)). © 2025 The Au

关键词： 6G Multi-objective routing Quadratic unconstrained binary optimization quantum approximate optimization algorithm quantum computing quantum optimization

来源：评论

学校读者我要写书评

暂无评论

quantum approximate optimization algorithm for Bayesian network structure learning

引用

quantum INFORMATION PROCESSING 2022年第1期22卷 1-28页

作者： Soloviev, Vicente P. Bielza, Concha Larranaga, Pedro Univ Politecn Madrid Computat Intelligence Grp Campus Montegancedo Madrid Spain

Bayesian network structure learning is an NP-hard problem that has been faced by a number of traditional approaches in recent decades. Currently, quantum technologies offer a wide range of advantages that can be exploited to solve optimization tasks that cannot be addressed in an efficient way when utilizing classic computing approaches. In this work, a specific type of variational quantum algorithm, the quantum approximate optimization algorithm, was used to solve the Bayesian network structure learning problem, by employing 3n(n - 1)/2 qubits, where n is the number of nodes in the Bayesian network to be learned. Our results showed that the quantum approximate optimization algorithm approach offers competitive results with stateof-the-art methods and quantitative resilience to quantum noise. The approach was applied to a cancer benchmark problem, and the results justified the use of variational quantum algorithms for solving the Bayesian network structure learning problem.

关键词： quantum approximate optimization algorithm Variational quantum algorithm quantum optimization Bayesian network structure learning

来源：评论

学校读者我要写书评

暂无评论

quantum approximate optimization algorithm with Sparsified Phase Operator 3

Quantum Approximate Optimization Algorithm with Sparsified P...

引用

3rd IEEE International Conference on quantum Computing and Engineering (QCE)

作者： Liu, Xiaoyuan Shaydulin, Ruslan Safro, Ilya Fujitsu Res Amer Inc Sunnyvale CA 94085 USA Univ Delaware Dept Comp & Informat Sci Newark DE 19716 USA Argonne Natl Lab Math & Comp Sci Div Lemont IL USA JPMorgan Chase Future Lab Appl Res & Engn New York NY USA

ISBN: (数字)9781665491136

ISBN: (纸本)9781665491136

The quantum approximate optimization algorithm (QAOA) is a promising candidate algorithm for demonstrating quantum advantage in optimization using near-term quantum computers. However, QAOA has high requirements on gate fidelity due to the need to encode the objective function in the phase separating operator, requiring a large number of gates that potentially do not match the hardware connectivity. Using the MaxCut problem as the target, we demonstrate numerically that an easier way to implement an alternative phase operator can be used in lieu of the phase operator encoding the objective function, as long as the ground state is the same. We observe that if the ground state energy is not preserved, the approximation ratio obtained by QAOA with such a phase separating operator is likely to decrease. Moreover, we show that a better alignment of the low energy subspace of the alternative operator leads to better performance. Leveraging these observations, we propose a sparsification strategy that reduces the resource requirements of QAOA. We also compare our sparsification strategy with some other classical graph sparsification methods and demonstrate the efficacy of our approach.

关键词： quantum computing quantum optimization quantum approximate optimization algorithm

来源：评论

学校读者我要写书评

暂无评论

quantum approximate optimization algorithm for PD-NOMA User Pairing

Quantum Approximate Optimization Algorithm for PD-NOMA User ...

引用

IEEE International Conference on Communications (IEEE ICC)

作者： Xiang, Qiwei Kho, Yau Hee Seah, Winston K. G. Tian, Yue Fang, Rui Huang, Peng Sichuan Agr Univ Coll Mech & Elect Engn Yaan Peoples R China Victoria Univ Wellington Sch Engn & Comp Sci Wellington 6140 New Zealand Xiamen Univ Technol Fujian Key Lab Commun Network & Informat Proc Xiamen 361024 Peoples R China

ISBN: (纸本)9781538674628

This work proposes the utilization of the quantum approximate optimization algorithm (QAOA) for user pairing in non-orthogonal multiple access (NOMA). By exploiting quantum concepts such as the quantum adiabatic theorem, a user pairing solution was derived that approximates a suboptimal sum rate. Moreover, an improved-QAOA is proposed to further enhance the performance by reducing the number of users in the cluster by dividing it into more clusters. Simulation results have demonstrated that the improved-QAOA yields a higher average achievable sum rate when compared to QAOA, and its solution is closer to the theoretical optimal value obtained by a brute-force enumeration method.

关键词： quantum approximate optimization algorithm Non-orthogonal multiple access 5G Wireless communications User pairing

来源：评论

学校读者我要写书评

暂无评论

Lower bounds on circuit depth of the quantum approximate optimization algorithm

引用

quantum INFORMATION PROCESSING 2021年第2期20卷 1-17页

作者： Herrman, Rebekah Ostrowski, James Humble, Travis S. Siopsis, George Univ Tennessee Dept Ind & Syst Engn Knoxville TN 37996 USA Oak Ridge Natl Lab Quantum Comp Inst Oak Ridge TN 37830 USA Univ Tennessee Dept Phys & Astron Knoxville TN 37996 USA

The quantum approximate optimization algorithm (QAOA) is a method of approximately solving combinatorial optimization problems. While QAOA is developed to solve a broad class of combinatorial optimization problems, it is not clear which classes of problems are best suited for it. One factor in demonstrating quantum advantage is the relationship between a problem instance and the circuit depth required to implement the QAOA method. As errors in noisy intermediate-scale quantum (NISQ) devices increase exponentially with circuit depth, identifying lower bounds on circuit depth can provide insights into when quantum advantage could be feasible. Here, we identify how the structure of problem instances can be used to identify lower bounds for circuit depth for each iteration of QAOA and examine the relationship between problem structure and the circuit depth for a variety of combinatorial optimization problems including MaxCut and MaxIndSet. Specifically, we show how to derive a graph, G, that describes a general combinatorial optimization problem and show that the depth of circuit is at least the chromatic index of G. By looking at the scaling of circuit depth, we argue that MaxCut, MaxIndSet, and some instances of vertex covering and Boolean satisfiability problems are suitable for QAOA approaches while knapsack and traveling salesperson problems are not.

关键词： quantum approximate optimization algorithm Circuit depth Combinatorial optimization Chromatic index

来源：评论

学校读者我要写书评

暂无评论

Unsupervised strategies for identifying optimal parameters in quantum approximate optimization algorithm

引用

EPJ quantum TECHNOLOGY 2022年第1期9卷 1-19页

作者： Moussa, Charles Wang, Hao Back, Thomas Dunjko, Vedran Leiden Univ LIACS Leiden Netherlands

As combinatorial optimization is one of the main quantum computing applications, many methods based on parameterized quantum circuits are being developed. In general, a set of parameters are being tweaked to optimize a cost function out of the quantum circuit output. One of these algorithms, the quantum approximate optimization algorithm stands out as a promising approach to tackling combinatorial problems. However, finding the appropriate parameters is a difficult task. Although QAOA exhibits concentration properties, they can depend on instances characteristics that may not be easy to identify, but may nonetheless offer useful information to find good parameters. In this work, we study unsupervised Machine Learning approaches for setting these parameters without optimization. We perform clustering with the angle values but also instances encodings (using instance features or the output of a variational graph autoencoder), and compare different approaches. These angle-finding strategies can be used to reduce calls to quantum circuits when leveraging QAOA as a subroutine. We showcase them within Recursive-QAOA up to depth 3 where the number of QAOA parameters used per iteration is limited to 3, achieving a median approximation ratio of 0.94 for MaxCut over 200 Erdos-Renyi graphs. We obtain similar performances to the case where we extensively optimize the angles, hence saving numerous circuit calls.

关键词： quantum computing Combinatorial optimization quantum approximate optimization algorithm Clustering

来源：评论

学校读者我要写书评

暂无评论

A quantum approximate optimization algorithm for solving Hamilton path problem

引用

JOURNAL OF SUPERCOMPUTING 2022年第13期78卷 15381-15403页

作者： Gong, Changqing Wang, Ting He, Wanying Qi, Han Shenyang Aerosp Univ Sch Comp Sci Daoyi Nan St Shenyang 110136 Liaoning Peoples R China

In recent years, combinatorial optimization has been widely studied. The existing optimization solutions are prone to fall into local optimal solutions and have a lower probability of obtaining global optimal solutions. quantum approximate optimization algorithm (QAOA) is an effective algorithm that can obtain the optimal solution with high probability. In this paper, the problem Hamiltonian is obtained by summing the problem function and the deformed constraints. Through theoretical formula derivation, the problem Hamiltonian is transformed into the Ising model. The performance of the experimental result under different optimizers and asynchronous lengths is verified on pyQPanda. The experimental results show that when using the problem Hamiltonian method set in this paper, the probability of obtaining the optimal solution is 99.59%. Compared with other methods, the proposed method can alleviate the risk of falling into local optimal solutions and obtain the global optimal solution with a higher probability.

关键词： quantum computing quantum approximate optimization algorithm Hamilton path Ising model

来源：评论

学校读者我要写书评

暂无评论

Classical symmetries and the quantum approximate optimization algorithm

引用

quantum INFORMATION PROCESSING 2021年第11期20卷 1-28页

作者： Shaydulin, Ruslan Hadfield, Stuart Hogg, Tad Safro, Ilya Argonne Natl Lab Lemont IL 60439 USA NASA Quantum Artificial Intelligence Lab QuAIL Ames Res Ctr Moffett Field CA 94035 USA KBR Houston TX 77002 USA USRA Res Inst Adv Comp Sci RIACS Mountain View CA 94043 USA Univ Delaware Comp & Informat Sci Newark DE 19716 USA

We study the relationship between the quantum approximate optimization algorithm (QAOA) and the underlying symmetries of the objective function to be optimized. Our approach formalizes the connection between quantum symmetry properties of the QAOA dynamics and the group of classical symmetries of the objective function. The connection is general and includes but is not limited to problems defined on graphs. We show a series of results exploring the connection and highlight examples of hard problem classes where a nontrivial symmetry subgroup can be obtained efficiently. In particular, we show how classical objective function symmetries lead to invariant measurement outcome probabilities across states connected by such symmetries, independent of the choice of algorithm parameters or number of layers. To illustrate the power of the developed connection, we apply machine learning techniques toward predicting QAOA performance based on symmetry considerations. We provide numerical evidence that a small set of graph symmetry properties suffices to predict the minimum QAOA depth required to achieve a target approximation ratio on the MaxCut problem, in a practically important setting where QAOA parameter schedules are constrained to be linear and hence easier to optimize.

关键词： quantum approximate optimization algorithm quantum optimization

来源：评论

学校读者我要写书评

暂无评论

quantum Linear System Solver Based on Time-optimal Adiabatic quantum Computing and quantum approximate optimization algorithm

引用

ACM TRANSACTIONS ON quantum COMPUTING 2022年第2期3卷 1–28页

作者： An, Dong Lin, Lin Univ Calif Berkeley Dept Math Berkeley CA 94720 USA Univ Calif Berkeley Challenge Inst Quantum Computat Berkeley CA 94720 USA Lawrence Berkeley Natl Lab Computat Res Div Berkeley CA 94720 USA

We demonstrate that with an optimally tuned scheduling function, adiabatic quantum computing (AQC) can readily solve a quantum linear system problem (QLSP) with O(kappa poly(log(kappa/epsilon))) runtime, where kappa is the condition number, and epsilon is the target accuracy. This is near optimal with respect to both kappa and epsilon, and is achieved without relying on complicated amplitude amplification procedures that are difficult to implement. Our method is applicable to general non-Hermitian matrices, and the cost as well as the number of qubits can be reduced when restricted to Hermitian matrices, and further to Hermitian positive definite matrices. The success of the time-optimal AQC implies that the quantum approximate optimization algorithm (QAOA) with an optimal control protocol can also achieve the same complexity in terms of the runtime. Numerical results indicate that QAOA can yield the lowest runtime compared to the time-optimal AQC, vanilla AQC, and the recently proposed randomization method.

关键词： quantum linear system problem adiabatic quantum computing quantum approximate optimization algorithm

来源：评论

学校读者我要写书评

暂无评论

Graph representation learning for parameter transferability in quantum approximate optimization algorithm

引用

quantum MACHINE INTELLIGENCE 2024年第2期6卷 1-16页

作者： Falla, Jose Langfitt, Quinn Alexeev, Yuri Safro, Ilya Univ Delaware Dept Phys & Astron Newark DE 19716 USA Univ Delaware Dept Comp & Informat Sci Newark DE 19716 USA Argonne Natl Lab Computat Sci Div Lemont IL 60439 USA

The quantum approximate optimization algorithm (QAOA) is one of the most promising candidates for achieving quantum advantage through quantum-enhanced combinatorial optimization. Optimal QAOA parameter concentration effects for special MaxCut problem instances have been observed, but a rigorous study of the subject is still lacking. Due to clustering of optimal QAOA parameters for MaxCut, successful parameter transferability between different MaxCut instances can be explained and predicted based on local properties of the graphs, including the type of subgraphs (lightcones) from which graphs are composed as well as the overall degree of nodes in the graph (parity). In this work, we apply five different graph embedding techniques to determine good donor candidates for parameter transferability, including parameter transferability between different classes of MaxCut instances. Using this technique, we effectively reduce the number of iterations required for parameter optimization, obtaining an approximate solution to the target problem with an order of magnitude speedup. This procedure also effectively removes the problem of encountering barren plateaus during the variational optimization of parameters. Additionally, our findings demonstrate that the transferred parameters maintain effectiveness when subjected to noise, supporting their use in real-world quantum applications. This work presents a framework for identifying classes of combinatorial optimization instances for which optimal donor candidates can be predicted such that QAOA can be substantially accelerated under both ideal and noisy conditions.

关键词： quantum computing quantum software quantum optimization quantum approximate optimization algorithm Parameter transferability Error mitigation

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：