astroquanta / qaoa_wsns

Repository for our paper on "Quantum Optimization of Wireless Sensor Networks"

QAOA_WSNs

Repository for our paper on "Quantum Optimization of Wireless Sensor Networks". With the development of wireless sensor networks to combat the problem of reaching places otherwise unreachable for humans, there is a need to keep these remote renewable devices charged. Optimizing the network to utilize the minimum amount of energy is the goal for any such network to be developed. We conducted this work in the context of a few wireless remote nodes used to charge an electrical/electronic moving device such as Electric Vehicles (EVs) and drones during flight. Our aim was to choose the path of minimum cost of reaching the destination device, thereby reducing the amount of charge expended by each node in the network. This problem falls under a larger umbrella of optimal path planning problems. These are Hamiltonian Cycle problems, a type of NP-Hard problem. There have been some research attempts to solve the problem, but often they are heuristic in nature and difficult to implement for any general case network. Due to the computational complexity (of the order of O(n!) due to maximum possible paths between nodes) of solving such an NP-Hard Problem, scaling up the network becomes quite difficult, which is needed for dense networks as they would be in large cities. We attempt to solve the problem using Quantum Algorithms. The advantage that quantum computing has over classical computing is due to the principle of superposition, an important postulate of quantum mechanics. In classical intuition, this allows parallel processing of data using a single processor of quantum computer (QPU). Quantum computing has the potential to beat classical computing in various contexts such as cryptography, molecular dynamics simulations and certain combinatorial problems like the travelling salesman problem. In this study, we perform a class of Variational quantum algorithms called Variational Quantum Eigensolver (VQE). The basics of these algorithms is that we design a cost function using a few parameters, which we can classically process, in the form of a Hamiltonian which we input into a quantum circuit to obtain the expectation value of this Hamiltonian. This expectation value would be a measure of the cost following which we can attempt to reduce the cost by using classical minimization techniques to reduce the cost for the next iteration of input into the quantum circuit. Now, VQE is a wide class of problems, particularly effective for the current NISQ (Noisy Intermediate State Quantum) era of quantum computing and has already been used in various applications such as drug design and protein structure analysis. VQE algorithms use something known as an ansatz for producing the output state of qubits from the input states. Designing the ansatz is very important and determines the specific solutions to the problem we are trying to solve. Now, the QAOA algorithm uses an ansatz specifically designed for solving combinatorial problems, which makes it an ideal candidate for implementing in the context of the above problem.