arXiv:2610.17145
On the Computational Complexity of Blind Quantum Machine Learning
Rex Fleur, Tzula B. Propp, Sebastian Feld
Abstract
Can quantum advantages in computational efficiency coexist with quantum advantages in privacy? In this paper, we construct and use MasonQ, a universal brickwork transpiler, to answer this question with a resounding yes. We approach this question by bridging two seemingly disparate paradigms: universal blind quantum computation (UBQC), based on measurement-based quantum computation, and quantum machine learning (QML) algorithms such as the Harrow-Hassidim-Lloyd (HHL) algorithm and quantum recommendation systems. We provide new upper bounds on the depth of UBQC brickwork graphs, establishing that $D = \mathcal{O}(ωn)$, where $ω$ is the circuit width and $n$ its computational gate complexity. This is enabled by our newly developed transpiler MasonQ, which maps arbitrary quantum circuits to computational brickwork graph states. Given an optimal Qiskit circuit as input, we prove optimality (up to logarithmic corrections) of the MasonQ transpiler in terms of asymptotic scaling of the total brickwork graph width and depth after decomposition into bricks, enabling systematic cost analyses of blind implementations in near-term experiments and asymptotic regimes. Leveraging MasonQ, we derive depth bounds for several representative blind quantum machine learning (B-QML) algorithms, including the quantum Fourier transform, the HHL algorithm, recommendation systems, and quantum transformers. Lastly, we analyze concrete resource estimates for near-term demonstrations of blind quantum machine learning. We propose a minimal B-QML implementation requiring only a $12$ qubit quantum server. To the best of our knowledge, MasonQ is the first functional and optimal universal circuit-to-brickwork-graph transpiler to implement the full brickwork transpilation process from first principles.
AI Summary
The paper asks how compiling quantum algorithms into universal blind quantum computation (UBQC) changes their computational resource scaling, focusing on quantum machine-learning routines. It introduces MasonQ, a Qiskit-to-Graphix transpiler that produces brickwork measurement patterns, measurement angles, and feedforward dependencies. For circuits with $n$ gates on $\omega$ logical qubits, comprising rotations, CX gates, and multi-controlled single-target $U(2)$ gates counted individually, it establishes brickwork depth $D=\mathcal{O}(\omega n)$ using one reusable clean ancilla. The construction combines nearest-neighbour routing, existing linear-cost multi-controlled-gate decompositions, and an alignment procedure that increases instruction-matrix depth by at most two. Optimality is established for fixed decompositions under specified placement and rotation-insertion constraints, rather than for unrestricted circuit compilation. A Solovay–Kitaev extension gives $D=\mathcal{O}(\omega n\log^\kappa(n/\varepsilon))$ for constant-locality gates. Applications give $\mathcal{O}(\log^3 N)$ depth for QFT, polylogarithmic dependence on matrix dimension for HHL under fixed sparsity, conditioning, and accuracy, and recommendation-system bounds of $\mathcal{O}(L^2\log L)$ including database encoding or $\mathcal{O}(\sqrt L\log L)$ for inference under assumed coherent access. Transpilation studies illustrate these scalings. A simulated two-entry recommendation example uses a six-row, 125-column graph: 750 remotely prepared states and 900 CZ gates, executable with 12 recycled server qubits. These are graph-depth bounds, not end-to-end runtime or classical-advantage demonstrations. Database preparation and coherent access remain assumptions in inference-only estimates; the proposed experiment requires sufficient coherence and fast remote preparation. The static encryption utility illustrates, rather than implements, full adaptive UBQC execution.
Central claim may not hold: The paper establishes conditional preservation of quantum algorithm scaling under compilation, not an end-to-end advantage over classical privacy-preserving learning under matched access and security assumptions. The exact O(ωn) theorem assumes specified counted gate families and an additional clean ancilla, whereas its stated general approximation extension includes a polylogarithmic accuracy overhead. The abstract's global width-and-depth optimality claim exceeds the proved optimality of scheduling a fixed decomposition under prescribed placement constraints. The specified eight-angle UBQC randomization leaks arbitrary computational angles modulo π/4, so it does not provide blindness for all exact arbitrary-angle patterns supported by MasonQ.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.