Dar Gilboa

The no-cloning theorem in quantum mechanics has been used as a basis for quantum money constructions, which guarantee unconditionally unforgeable currency. Existing schemes, however, either (i) require long-term quantum memory and quantum communication between the user and the bank in order to verify the validity of a bill or (ii) fail to protect user privacy due to the uniqueness of each bill issued by the bank, which can allow its usage to be tracked. We introduce a construction of single-use quantum money that gives users the ability to detect whether the issuing authority is tracking them, employing an auditing procedure for which we prove unconditional security. The use of our scheme does not require long-term quantum memory or quantum communication from the users themselves since their validation is a purely classical operation, making the protocol relatively practical to deploy. We discuss potential applications beyond money, including anonymous one-time pads and voting.

Quantum computers are believed to provide expo- nential speedups in solving certain classes of opti- mization problems, with the recently introduced Decoded Quantum Interferometry (DQI) frame- work (Jordan et al., 2025) providing a template for discovering novel applications of this form. Since many quantum speedups apply only to discrete problems with algebraic structure, it is of great in- terest to understand when speedups are possible in less structured settings that more closely resemble natural problems. We consider constraint satisfac- tion problems with continuous, unstructured con- straints that are inspired by problems in machine learning. We analyze the performance of a quan- tum algorithm based on DQI that leverages the sparse recovery guarantees of compressed sens- ing. We prove that this approach outperforms certain classical algorithms with provable guar- antees, and suggest regimes where it might also outperform classical heuristic algorithms like sim- ulated annealing. Our work presents a novel way in which the powerful toolkit of continuous sparse recovery algorithms can be used to design novel quantum algorithms.