# Enigma: Application-Layer Privacy for Quantum Optimization on Untrusted Computers

arXiv: https://arxiv.org/abs/2311.13546 · HTML: https://mlsanity.com/paper/2311.13546/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 96 references that are in the map.
- First posted on arXiv 22 Nov 2023.

## Builds on (most cited first, 21 of 21)

- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [Supervised Contrastive Learning](https://mlsanity.com/paper/2004.11362/) (2020)
- [Deep metric learning using Triplet network](https://mlsanity.com/paper/1412.6622/) (2014)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties](https://mlsanity.com/paper/1811.02834/) (2018)
- [A Survey on Metric Learning for Feature Vectors and Structured Data](https://mlsanity.com/paper/1306.6709/) (2013)
- [NetLSD: Hearing the Shape of a Graph](https://mlsanity.com/paper/1805.10712/) (2018)
- [Scale-free networks are rare](https://mlsanity.com/paper/1801.03400/) (2018)
- [Private quantum computation: An introduction to blind quantum computing and related protocols](https://mlsanity.com/paper/1611.10107/) (2016)
- [Quantum Computing at the Frontiers of Biological Sciences](https://mlsanity.com/paper/1911.07127/) (2019)
- [Quantum Computing for Power Flow Algorithms: Testing on real Quantum Computers](https://mlsanity.com/paper/2204.14028/) (2022)
- [Quantum homomorphic encryption for polynomial-sized circuits](https://mlsanity.com/paper/1603.09717/) (2016)
- [An Ensemble Approach for Compressive Sensing with Quantum](https://mlsanity.com/paper/2006.04682/) (2020)
- [FrozenQubits: Boosting Fidelity of QAOA by Skipping Hotspot Nodes](https://mlsanity.com/paper/2210.17037/) (2022)
- [Super-blockers and the effect of network structure on information cascades](https://mlsanity.com/paper/1802.05039/) (2018)
- [Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem](https://mlsanity.com/paper/1906.10036/) (2019)
- [EQUAL: Improving the Fidelity of Quantum Annealers by Injecting Controlled Perturbations](https://mlsanity.com/paper/2108.10964/) (2021)
- [Limitations on information theoretically secure quantum homomorphic encryption](https://mlsanity.com/paper/1406.2456/) (2014)
- [A quantum approach to homomorphic encryption](https://mlsanity.com/paper/1411.5254/) (2014)
- [Power network optimization: a quantum approach](https://mlsanity.com/paper/2212.01625/) (2022)

## Built on by (most cited first, 2 of 2)

- [Guardians of the Quantum GAN](https://mlsanity.com/paper/2404.16156/) (2024)
- [Security Concerns in Quantum Machine Learning as a Service](https://mlsanity.com/paper/2408.09562/) (2024)

## Abstract (arXiv)

The Early Fault-Tolerant (EFT) era is emerging, where modest Quantum Error Correction (QEC) can enable quantum utility before full-scale fault tolerance. Quantum optimization is a leading candidate for early applications, but protecting these workloads is critical since they will run on expensive cloud services where providers could learn sensitive problem details. Experience with classical computing systems has shown that treating security as an afterthought can lead to significant vulnerabilities. Thus, we must address the security implications of quantum computing before widespread adoption. However, current Secure Quantum Computing (SQC) approaches, although theoretically promising, are impractical in the EFT era: blind quantum computing requires large-scale quantum networks, and quantum homomorphic encryption depends on full QEC. We propose application-specific SQC, a principle that applies obfuscation at the application layer to enable practical deployment while remaining agnostic to algorithms, computing models, and hardware architectures. We present Enigma, the first realization of this principle for quantum optimization. Enigma integrates three complementary obfuscations: ValueGuard scrambles coefficients, StructureCamouflage inserts decoys, and TopologyTrimmer prunes variables. These techniques guarantee recovery of original solutions, and their stochastic nature resists repository-matching attacks. Evaluated against seven state-of-the-art AI models across five representative graph families, even combined adversaries, under a conservatively strong attacker model, identify the correct problem within their top five guesses in only 4.4% of cases. The protections come at the cost of problem size and T-gate counts increasing by averages of 1.07x and 1.13x, respectively, with both obfuscation and decoding completing within seconds for large-scale problems.