We investigate the relevance of variational algorithms for the single-source single-destination shortest path problem, within the application framework of eco-routing. The problem is formulated via a Quadratic Unconstrained Binary Optimization (QUBO) model, which is solved using VQE and QAOA algorithms. For QAOA two different initialization schemes are tested, based on a heuristic strategy, whereas for VQE we test two different ansatzes. The results highlight both the feasibility and scalability issues of solving the shortest path problem with quantum optimization approaches, while providing a simple yet interesting comparison between VQE and QAOA. This work aims to establish an initial direction towards addressing more challenging constrained variants of the problem.We investigate the relevance of variational algorithms for the single-source single-destination shortest path problem, within the application framework of eco-routing. The problem is formulated via a Quadratic Unconstrained Binary Optimization (QUBO) model, which is solved using VQE and QAOA algorithms. For QAOA two different initialization schemes are tested, based on a heuristic strategy, whereas for VQE we test two different ansatzes. The results highlight both the feasibility and scalability issues of solving the shortest path problem with quantum optimization approaches, while providing a simple yet interesting comparison between VQE and QAOA. This work aims to establish an initial direction towards addressing more challenging constrained variants of the problem.

Apr 24, 20260 citations

Value of the VQE

H.G.H. Dixon

Production EngineerJan 1, 19740 citations

Value of the VQE

Hayley Dixon

Production EngineerJan 1, 19740 citations

Comparison of quantum computing algorithms for network traffic partitioning and mitigation of DoS and DDoS attacks

Casimer M. DeCusatis, Evan Spillane, Dominick P. Foti +1 more

We investigate application of quantum computing algorithms to classifying network traffic and mitigating denial of service and distributed denial of service attacks. Using actual honeynet data, we compare solutions of the Max Cut problem using both the quantum approximate optimization algorithm (QAOA) and Variational Quantum Eigensolver (VQE). Experimental results from a 6-qubit quantum computer show that optimal solutions can be found with about 98% accuracy in polynomial execution time. We found that VQE is more accurate than QAOA (compared with classical brute force solutions) but also requires significantly longer execution times. Simulations predict this approach can scale to much larger quantum computing hardware (when available) and may achieve quantum advantage on hardware with 30-35 qubits.We investigate application of quantum computing algorithms to classifying network traffic and mitigating denial of service and distributed denial of service attacks. Using actual honeynet data, we compare solutions of the Max Cut problem using both the quantum approximate optimization algorithm (QAOA) and Variational Quantum Eigensolver (VQE). Experimental results from a 6-qubit quantum computer show that optimal solutions can be found with about 98% accuracy in polynomial execution time. We found that VQE is more accurate than QAOA (compared with classical brute force solutions) but also requires significantly longer execution times. Simulations predict this approach can scale to much larger quantum computing hardware (when available) and may achieve quantum advantage on hardware with 30-35 qubits.

IEEE Annual Ubiquitous Computing, Electronics & Mobile Communication Conference (UEMCON)Oct 17, 20241 citation

Evaluating the performance of the Quantum Approximate Optimisation Algorithm to solve the Quadratic Assignment Problem

M. T. Khumalo, Krupa Prag, Ken J. Nixon

The performance of the Quantum Approximate Optimisation Algorithm (QAOA) in solving the Quadratic Assignment Problem (QAP) is evaluated, with the Variational Quantum Eigensolver (VQE) as a benchmark. The QAP is directly revelant to numerous industry scenarios. The QAP, a Combinatorial Optimisation Problem (COP), is classified as $\mathcal{NP}$ -Hard. This classification means CPU time increases exponentially as the problem size scales when solving the QAP using deterministic optimisation techniques. Therefore, this work investigates the QAOA in search of a non-deterministic optimisation technique to efficiently obtain solutions to the QAP. This research compares two warm start techniques to solve QAP instances of sizes 3 to 7. The metrics of comparison - that measure efficiency and solution quality - were introduced in previous work on this topic. For the QAOA, the impact of the p-value, a determination of circuit depth, is investigated. Of the two quantum hybrid heuristics, the VQE retrieves solutions in a shorter computational time with a smaller circuit size, which allows for solving instances with a larger problem size. Compared to the VQE, the QAOA performs better in terms of feasibility as the problem size scales. The quantum warm start method results implies that the QAOA may not maintain higher solution quality for instances larger than size 4. Still, further investigation should be conducted once quantum devices with more qubits and higher quantum volumes are available.The performance of the Quantum Approximate Optimisation Algorithm (QAOA) in solving the Quadratic Assignment Problem (QAP) is evaluated, with the Variational Quantum Eigensolver (VQE) as a benchmark. The QAP is directly revelant to numerous industry scenarios. The QAP, a Combinatorial Optimisation Problem (COP), is classified as$\mathcal{NP}$-Hard. This classification means CPU time increases exponentially as the problem size scales when solving the QAP using deterministic optimisation techniques. Therefore, this work investigates the QAOA in search of a non-deterministic optimisation technique to efficiently obtain solutions to the QAP. This research compares two warm start techniques to solve QAP instances of sizes 3 to 7. The metrics of comparison - that measure efficiency and solution quality - were introduced in previous work on this topic. For the QAOA, the impact of the p-value, a determination of circuit depth, is investigated. Of the two quantum hybrid heuristics, the VQE retrieves solutions in a shorter computational time with a smaller circuit size, which allows for solving instances with a larger problem size. Compared to the VQE, the QAOA performs better in terms of feasibility as the problem size scales. The quantum warm start method results implies that the QAOA may not maintain higher solution quality for instances larger than size 4. Still, further investigation should be conducted once quantum devices with more qubits and higher quantum volumes are available.

International Conference on Soft Computing & Machine Intelligence (ISCMI)Nov 26, 20220 citations

\mathcal{NP}

-Hard. This classification means CPU time increases exponentially as the problem size scales when solving the QAP using deterministic optimisation techniques. Therefore, this work investigates the QAOA in search of a non-deterministic optimisation technique to efficiently obtain solutions to the QAP. This research compares two warm start techniques to solve QAP instances of sizes 3 to 7. The metrics of comparison - that measure efficiency and solution quality - were introduced in previous work on this topic. For the QAOA, the impact of the p-value, a determination of circuit depth, is investigated. Of the two quantum hybrid heuristics, the VQE retrieves solutions in a shorter computational time with a smaller circuit size, which allows for solving instances with a larger problem size. Compared to the VQE, the QAOA performs better in terms of feasibility as the problem size scales. The quantum warm start method results implies that the QAOA may not maintain higher solution quality for instances larger than size 4. Still, further investigation should be conducted once quantum devices with more qubits and higher quantum volumes are available.