All Your Base Are Belong To Us: Stealing VRP Secrets from Quantum Circuit Structures

The security and confidentiality of sensitive information processed by quantum computers are of paramount concerns, especially given quantum computers' potential to efficiently solve classically-hard optimization problems. At the heart of many transport optimization tasks lies the Vehicle Routing Problem (VRP), a complex combinatorial optimization issue classified as NP-hard. However, a promising avenue for approximating solutions to VRP is found in the Quantum Approximate Optimization Algorithm (QAOA). This paper demonstrates that analyzing the QAOA quantum circuit structure enables inference of the problem being solved, such as the location or connection of military bases in routing optimization scenarios. By exploiting information leakage, say from side channels, during the QAOA execution, attackers can potentially breach security and retrieve sensitive VRP details, posing profound implications for civilian and national security. This study underscores the need to address and mitigate side-channel vulnerabilities in quantum computing systems to safeguard sensitive information.