Complexity Amplification from Compression in Quantum Random Access Optimization
The study investigates how compressing classical optimization problems using Quantum Random Access Optimization (QRAO) encoding can drastically increase computational difficulty, potentially moving solvable problems from NP to QMA complexity. It shows that the compression process itself creates worst-case barriers, meaning simply reducing qubits does not guarantee easier computation.