quantum-computing

An access model for quantum encoded data

Quantum Journal

22 min read

0 likes

⚡ Quantum Brief

Researchers introduced the approximate sample and query (ASQ) model, a new data access framework for quantum-encoded states that bridges quantum and classical computation. The model enables polynomial-time operations via block encoding, Pauli sampling, or classical circuit simulation. The ASQ model proves compositional, allowing linear combinations of quantum states and approximate inner product computations. While weaker than classical dequantization results, it retains computational power and supports fault-tolerant quantum circuits with classical assistance. Applied to distributed inner product estimation, ASQ achieves polynomial improvements in sample and computational complexity. This reframes Pauli sampling’s utility by linking entanglement measures to state sparsity in measurement bases. Unlike prior work focusing on classical input data, this model addresses quantum input data—where only non-entangled state copies are accessible. Logarithmic-depth quantum manipulations suffice to satisfy its "promises" before measurement. The findings mark a first step toward extending Quantum Singular Value Transform dequantization to quantum settings, partially characterizing the power of time-limited, hybrid quantum-classical systems.

An access model for quantum encoded data

Summarize this article with:

AbstractWe introduce and investigate a data access model $\textit{(approximate sample and query)}$ that is satisfiable by the preparation and measurement of block encoded states, as well as in contexts such as classical quantum circuit simulation or Pauli sampling. We illustrate that this abstraction is compositional and has some computational power. We then apply these results to obtain polynomial improvements over the state of the art in the sample and computational complexity of distributed inner product estimation. By doing so, we provide a new interpretation for why Pauli sampling is useful for this task. Our results partially characterize the power of time-limited fault-tolerant quantum circuits aided by classical computation. They are a first step towards extending the classical data Quantum Singular Value Transform dequantization results to a quantum setting.Featured image: The approximate sample and query (ASQ) access model restricts access to a vector to three rules. These can be satisfied by quantum or classical agents in the right conditions. By developing algorithms that operate over this abstraction, their runtime can be described in terms of the time necessary to carry out each access operation. If a classical agent can satisfy each operation fast enough, a dequantization result follows. In this paper, we establish some of the power of ASQ: we show that an agent can compose ASQ into linear combinations, and that they can use ASQ access to compute the inner product.Popular summaryQuantum computers are as powerful as classical computers, and there is strong evidence for a quantum advantage. However, it is not always clear where this advantage comes from, and it was shown for some quantum algorithms that the "quantumness" could be removed (to produce quantum-inspired, but classical, algorithms; this may be referred to "dequantization"). For both theoretical and practical reasons, it would be useful to understand where "quantumness" can be removed or is essential. At the same time, it has been shown that many quantum algorithms, which are apparently dissimilar, can be unified under a single conceptual framework (Quantum Singular Value Transformations, QSVTs). Thus, to examine how to dequantize QSVT algorithms is also to examine how to dequantize a number of key quantum algorithms. Other authors have tackled this issue with a two-step approach: first, they reduced quantum power to a set of promises to be satisfied using the quantum computer and showed that these promises can be satisfied with as much effort classically. Then, they showed that this set of promises sufficed to simulate measurements of QSVTs without too much overhead. Examining the details of these "promises", one finds that they in fact require genuine classical access to what would be the quantum state representation in the measurement basis. This is, therefore, a classical input data case, where the quantum state reflects only some classical data to which access is also given. In this work, we examine the quantum input data case, where one is only given non-entangled copies of an input quantum state. To study this case, we modify the access model as little as possible, but enough so that the new "promises" can be satisfied with logarithmic-depth manipulation of the quantum state before measurement. We show that the new access model remains interesting, by showing that it retains two key properties: composition and computation. By composition, we mean that being able to satisfy the access model for $A$ and $B$ is enough to simulate access to $A+B$. By computation, we mean that being able to satisfy the access model to $A$ and $B$ is enough to approximately compute $A^\dagger B$. Our results are weaker than those obtained for classical input data, as there are always states that will make both composition and computation inefficient; however, this is expected (and required) from previously known results. To show that the introduced access model is useful, both for understanding and simplifying the proof of some results, we apply it to the problem of distributed inner product estimation: two parties can communicate classically, each has access to some state, and both jointly wish to compute the fidelity between their respective states. This problem is recognised as significant, and is important, for example, for fidelity estimation. Through the formulation of the problem in the terms we propose, we show that previous connections between self-entanglement measures and the computational hardness of this task can be understood from the direct connection between the entanglement measure and the sparseness of the state in a measurement basis. By employing the same logic, we slightly strengthen the result.► BibTeX data@article{Murca2026accessmodelquantum, doi = {10.22331/q-2026-03-16-2028}, url = {https://doi.org/10.22331/q-2026-03-16-2028}, title = {An access model for quantum encoded data}, author = {Mur{\c{c}}a, Miguel and K. Faehrmann, Paul and Omar, Yasser}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2028}, month = mar, year = {2026} }► References [1] Rajeev Acharya, Igor Aleiner, Richard Allen, Ningfeng Zhu, et al. ``Suppressing quantum errors by scaling a surface code logical qubit''. Nature 614, 676–681 (2023). https://doi.org/10.1038/s41586-022-05434-1 [2] M. DeCross, R. Haghshenas, M. Foss-Feig, et al. ``Computational power of random quantum circuits in arbitrary geometries''. Phys. Rev. X 15, 021052 (2025). https://doi.org/10.1103/PhysRevX.15.021052 [3] Craig Gidney, Noah Shutty, and Cody Jones. ``Magic state cultivation: growing T states as cheap as CNOT gates''. Unpublished. (2024) arXiv:2409.17595. arXiv:2409.17595 [4] Benjamin L. Brock, Shraddha Singh, Devoret, Michel H., et al. ``Quantum error correction of qudits beyond break-even''. Nature 641, 612–618 (2025). https://doi.org/10.1038/s41586-025-08899-y [5] Rajeev Acharya, Dmitry A. Abanin, Zobrist, Nicholas, et al. ``Quantum error correction below the surface code threshold''. Nature 638, 920–926 (2024). https://doi.org/10.1038/s41586-024-08449-y [6] Adam Wills, Min-Hsiu Hsieh, and Hayata Yamasaki. ``Constant-overhead magic state distillation''. Nature Physics 21, 1842–1846 (2025). https://doi.org/10.1038/s41567-025-03026-0 [7] Hengyun Zhou, Chen Zhao, Mikhail D. Lukin, et al. ``Low-overhead transversal fault tolerance for universal quantum computation''. Nature 646, 303–308 (2025). https://doi.org/10.1038/s41586-025-09543-5 [8] Abhinav Kandala, Antonio Mezzacapo, Jay M. Gambetta, et al. ``Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets''. Nature 549, 242–246 (2017). https://doi.org/10.1038/nature23879 [9] M. Cerezo, Guillaume Verdon, Hsin-Yuan Huang, Lukasz Cincio, and Patrick J. Coles. ``Challenges and opportunities in quantum machine learning''.

Nature Computational Science 2, 567–576 (2022). https://doi.org/10.1038/s43588-022-00311-3 [10] Kishor Bharti, Alba Cervera-Lierta, Alán Aspuru-Guzik, et al. ``Noisy intermediate-scale quantum algorithms''. Reviews of Modern Physics 94 (2022). https://doi.org/10.1103/revmodphys.94.015004 [11] Jarrod R. McClean, Sergio Boixo, Hartmut Neven, et al. ``Barren plateaus in quantum neural network training landscapes''. Nature Communications 9 (2018). https://doi.org/10.1038/s41467-018-07090-4 [12] Martín Larocca, Supanut Thanasilp, M. Cerezo, et al. ``Barren plateaus in variational quantum computing''.

Nature Reviews Physics 7, 174–189 (2025). https://doi.org/10.1038/s42254-025-00813-9 [13] Thomas Häner and Damian S. Steiger. ``0.5 petabyte simulation of a 45-qubit quantum circuit''. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. SC '17. ACM (2017). https://doi.org/10.1145/3126908.3126947 [14] Cupjin Huang, Fang Zhang, Michael Newman, Mario Szegedy, Jianxin Chen, et al. ``Classical simulation of quantum supremacy circuits''. Unpublished. (2020) arXiv:2005.06787. arXiv:2005.06787 [15] Igor L. Markov, Aneeqa Fatima, Sergei V. Isakov, and Sergio Boixo. ``Massively parallel approximate simulation of hard quantum circuits''. In 2020 57th ACM/IEEE Design Automation Conference (DAC). Pages 1–6. IEEE (2020). https://doi.org/10.1109/dac18072.2020.9218591 [16] Begušić Tomislav and Garnet Kin-Lic Chan. ``Fast classical simulation of evidence for the utility of quantum computing before fault tolerance''. Unpublished. (2023) arXiv:2306.16372. arXiv:2306.16372 [17] Hsin-Yuan Huang, Richard Kueng, and John Preskill. ``Predicting many properties of a quantum system from very few measurements''. Nature Physics 16, 1050–1057 (2020). https://doi.org/10.1038/s41567-020-0932-7 [18] Hsin-Yuan Huang, Michael Broughton, Jarrod R. McClean, et al. ``Power of data in quantum machine learning''. Nature Communications 12 (2021). https://doi.org/10.1038/s41467-021-22539-9 [19] Hsin-Yuan Huang, Michael Broughton, Jarrod R. McClean, et al. ``Quantum advantage in learning from experiments''. Science 376, 1182–1186 (2022). https://doi.org/10.1126/science.abn7293 [20] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. ``The complexity of nisq''. Nature Communications 14 (2023). https://doi.org/10.1038/s41467-023-41217-6 [21] Ethan Bernstein and Umesh Vazirani. ``Quantum complexity theory''. SIAM Journal on Computing 26, 1411–1473 (1997). https://doi.org/10.1137/s0097539796300921 [22] Scott Aaronson and Andris Ambainis. ``Forrelation: A problem that optimally separates quantum from classical computing''. In Proceedings of the forty-seventh annual ACM symposium on Theory of Computing. STOC '15. ACM (2015). https://doi.org/10.1145/2746539.2746547 [23] Xiaoming Sun and Yufan Zheng. ``Hybrid decision trees: Longer quantum time is strictly more powerful''. Unpublished. (2019) arXiv:1911.13091. arXiv:1911.13091 [24] Maarten Van Den Nest. ``Simulating quantum computers with probabilistic methods''. Quantum Info. Comput. 11, 784–812 (2011). [25] Ewin Tang. ``A quantum-inspired classical algorithm for recommendation systems''. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC '19. ACM (2019). https://doi.org/10.1145/3313276.3316310 [26] Nai-Hui Chia, András Gilyén, Chunhao Wang, et al. ``Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning''. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. ACM (2020). [27] François Le Gall. ``Robust dequantization of the quantum singular value transformation and quantum machine learning algorithms''. computational complexity 34 (2025). https://doi.org/10.1007/s00037-024-00262-3 [28] Scott Aaronson and Daniel Gottesman. ``Improved simulation of stabilizer circuits''. Physical Review A 70 (2004). https://doi.org/10.1103/physreva.70.052328 [29] Leslie G. Valiant. ``Quantum circuits that can be simulated classically in polynomial time''. SIAM Journal on Computing 31, 1229–1254 (2002). https://doi.org/10.1137/s0097539700377025 [30] Daniel R. Simon. ``On the power of quantum computation''. SIAM Journal on Computing 26, 1474–1483 (1997). https://doi.org/10.1137/s0097539796298637 [31] P.W. Shor. ``Algorithms for quantum computation: discrete logarithms and factoring''. In Proceedings 35th Annual Symposium on Foundations of Computer Science. Pages 124–134. SFCS-94. IEEE Comput. Soc. Press (1994). https://doi.org/10.1109/sfcs.1994.365700 [32] P. Dagum, R. Karp, M. Luby, and S. Ross. ``An optimal algorithm for monte carlo estimation''. In Proceedings of IEEE 36th Annual Foundations of Computer Science. Pages 142–149. (1995). https://doi.org/10.1109/SFCS.1995.492471 [33] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics''. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC '19. ACM (2019). https://doi.org/10.1145/3313276.3316366 [34] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. ``Quantum amplitude amplification and estimation'' (2002). [35] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for linear systems of equations''.

Physical Review Letters 103 (2009). https://doi.org/10.1103/physrevlett.103.150502 [36] Andrew M. Childs and Nathan Wiebe. ``Hamiltonian simulation using linear combinations of unitary operations''. Quantum Information and Computation 12 (2012). https://doi.org/10.26421/qic12.11-12 [37] Jordan Cotler, Hsin-Yuan Huang, and Jarrod R. McClean. ``Revisiting dequantization and quantum advantage in learning tasks''. Unpublished. (2021) arXiv:2112.00811. arXiv:2112.00811 [38] Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, and Giacomo Nannicini. ``Quantum tomography using state-preparation unitaries''. Pages 1265–1318. Society for Industrial and Applied Mathematics. (2023). https://doi.org/10.1137/1.9781611977554.ch47 [39] Sergey Bravyi and David Gosset. ``Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates''.

Physical Review Letters 116, 250501 (2016). https://doi.org/10.1103/PhysRevLett.116.250501 [40] Anurag Anshu, Zeph Landau, and Yunchao Liu. ``Distributed quantum inner product estimation''. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. STOC '22. ACM (2022). https://doi.org/10.1145/3519935.3519974 [41] M. Hinsche, M. Ioannou, S. Jerbi, L. Leone, J. Eisert, and J. Carrasco. ``Efficient distributed inner-product estimation via pauli sampling''. PRX Quantum 6, 030354 (2025). https://doi.org/10.1103/g53f-z8cr [42] Earl T. Campbell. ``Catalysis and activation of magic states in fault-tolerant architectures''. Physical Review A 83 (2011). https://doi.org/10.1103/physreva.83.032317 [43] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. ``Stabilizer rényi entropy''.

Physical Review Letters 128 (2022). https://doi.org/10.1103/physrevlett.128.050402 [44] Donald E. Knuth. ``Big omicron and big omega and big theta''. ACM SIGACT News 8, 18–24 (1976). https://doi.org/10.1145/1008328.1008329 [45] Sanjeev Arora and Boaz Barak. ``Computational complexity: A modern approach''.

Cambridge University Press. USA (2009). 1st edition. [46] Vivek V. Shende, Aditya K. Prasad, Igor L. Markov, and John P. Hayes. ``Reversible logic circuit synthesis''. In Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design - ICCAD '02. Pages 353–360. ICCAD '02. ACM Press (2002). https://doi.org/10.1145/774572.774625 [47] Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, and Jerry Li. ``Exponential separations between learning with and without quantum memory''. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). Volume 169, pages 574–585. IEEE (2022). https://doi.org/10.1109/focs52979.2021.00063 [48] Steven T. Flammia and Yi-Kai Liu. ``Direct fidelity estimation from few pauli measurements''.

Physical Review Letters 106 (2011). https://doi.org/10.1103/physrevlett.106.230501 [49] M. Van den Nest. ``Classical simulation of quantum computation, the gottesman-knill theorem, and slightly beyond''. Quantum Information and Computation 10, 258–271 (2010). https://doi.org/10.26421/qic10.3-4-6 [50] Masashi Okamoto. ``Some inequalities relating to the partial sum of binomial probabilities''. Annals of the Institute of Statistical Mathematics 10, 29–35 (1959). https://doi.org/10.1007/bf02883985 [51] Srinivasan Arunachalam and Louis Schatzki. ``Distributed inner product estimation with limited quantum communication''. Unpublished. (2024) arXiv:2410.12684. arXiv:2410.12684 [52] Weiyuan Gong, Jonas Haferkamp, Qi Ye, and Zhihan Zhang. ``On the sample complexity of purity and inner product estimation''. Unpublished. (2024) arXiv:2410.12712. arXiv:2410.12712Cited byCould not fetch Crossref cited-by data during last attempt 2026-03-16 08:07:44: Could not fetch cited-by data for 10.22331/q-2026-03-16-2028 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-03-16 08:07:44: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractWe introduce and investigate a data access model $\textit{(approximate sample and query)}$ that is satisfiable by the preparation and measurement of block encoded states, as well as in contexts such as classical quantum circuit simulation or Pauli sampling. We illustrate that this abstraction is compositional and has some computational power. We then apply these results to obtain polynomial improvements over the state of the art in the sample and computational complexity of distributed inner product estimation. By doing so, we provide a new interpretation for why Pauli sampling is useful for this task. Our results partially characterize the power of time-limited fault-tolerant quantum circuits aided by classical computation. They are a first step towards extending the classical data Quantum Singular Value Transform dequantization results to a quantum setting.Featured image: The approximate sample and query (ASQ) access model restricts access to a vector to three rules. These can be satisfied by quantum or classical agents in the right conditions. By developing algorithms that operate over this abstraction, their runtime can be described in terms of the time necessary to carry out each access operation. If a classical agent can satisfy each operation fast enough, a dequantization result follows. In this paper, we establish some of the power of ASQ: we show that an agent can compose ASQ into linear combinations, and that they can use ASQ access to compute the inner product.Popular summaryQuantum computers are as powerful as classical computers, and there is strong evidence for a quantum advantage. However, it is not always clear where this advantage comes from, and it was shown for some quantum algorithms that the "quantumness" could be removed (to produce quantum-inspired, but classical, algorithms; this may be referred to "dequantization"). For both theoretical and practical reasons, it would be useful to understand where "quantumness" can be removed or is essential. At the same time, it has been shown that many quantum algorithms, which are apparently dissimilar, can be unified under a single conceptual framework (Quantum Singular Value Transformations, QSVTs). Thus, to examine how to dequantize QSVT algorithms is also to examine how to dequantize a number of key quantum algorithms. Other authors have tackled this issue with a two-step approach: first, they reduced quantum power to a set of promises to be satisfied using the quantum computer and showed that these promises can be satisfied with as much effort classically. Then, they showed that this set of promises sufficed to simulate measurements of QSVTs without too much overhead. Examining the details of these "promises", one finds that they in fact require genuine classical access to what would be the quantum state representation in the measurement basis. This is, therefore, a classical input data case, where the quantum state reflects only some classical data to which access is also given. In this work, we examine the quantum input data case, where one is only given non-entangled copies of an input quantum state. To study this case, we modify the access model as little as possible, but enough so that the new "promises" can be satisfied with logarithmic-depth manipulation of the quantum state before measurement. We show that the new access model remains interesting, by showing that it retains two key properties: composition and computation. By composition, we mean that being able to satisfy the access model for $A$ and $B$ is enough to simulate access to $A+B$. By computation, we mean that being able to satisfy the access model to $A$ and $B$ is enough to approximately compute $A^\dagger B$. Our results are weaker than those obtained for classical input data, as there are always states that will make both composition and computation inefficient; however, this is expected (and required) from previously known results. To show that the introduced access model is useful, both for understanding and simplifying the proof of some results, we apply it to the problem of distributed inner product estimation: two parties can communicate classically, each has access to some state, and both jointly wish to compute the fidelity between their respective states. This problem is recognised as significant, and is important, for example, for fidelity estimation. Through the formulation of the problem in the terms we propose, we show that previous connections between self-entanglement measures and the computational hardness of this task can be understood from the direct connection between the entanglement measure and the sparseness of the state in a measurement basis. By employing the same logic, we slightly strengthen the result.► BibTeX data@article{Murca2026accessmodelquantum, doi = {10.22331/q-2026-03-16-2028}, url = {https://doi.org/10.22331/q-2026-03-16-2028}, title = {An access model for quantum encoded data}, author = {Mur{\c{c}}a, Miguel and K. Faehrmann, Paul and Omar, Yasser}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2028}, month = mar, year = {2026} }► References [1] Rajeev Acharya, Igor Aleiner, Richard Allen, Ningfeng Zhu, et al. ``Suppressing quantum errors by scaling a surface code logical qubit''. Nature 614, 676–681 (2023). https://doi.org/10.1038/s41586-022-05434-1 [2] M. DeCross, R. Haghshenas, M. Foss-Feig, et al. ``Computational power of random quantum circuits in arbitrary geometries''. Phys. Rev. X 15, 021052 (2025). https://doi.org/10.1103/PhysRevX.15.021052 [3] Craig Gidney, Noah Shutty, and Cody Jones. ``Magic state cultivation: growing T states as cheap as CNOT gates''. Unpublished. (2024) arXiv:2409.17595. arXiv:2409.17595 [4] Benjamin L. Brock, Shraddha Singh, Devoret, Michel H., et al. ``Quantum error correction of qudits beyond break-even''. Nature 641, 612–618 (2025). https://doi.org/10.1038/s41586-025-08899-y [5] Rajeev Acharya, Dmitry A. Abanin, Zobrist, Nicholas, et al. ``Quantum error correction below the surface code threshold''. Nature 638, 920–926 (2024). https://doi.org/10.1038/s41586-024-08449-y [6] Adam Wills, Min-Hsiu Hsieh, and Hayata Yamasaki. ``Constant-overhead magic state distillation''. Nature Physics 21, 1842–1846 (2025). https://doi.org/10.1038/s41567-025-03026-0 [7] Hengyun Zhou, Chen Zhao, Mikhail D. Lukin, et al. ``Low-overhead transversal fault tolerance for universal quantum computation''. Nature 646, 303–308 (2025). https://doi.org/10.1038/s41586-025-09543-5 [8] Abhinav Kandala, Antonio Mezzacapo, Jay M. Gambetta, et al. ``Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets''. Nature 549, 242–246 (2017). https://doi.org/10.1038/nature23879 [9] M. Cerezo, Guillaume Verdon, Hsin-Yuan Huang, Lukasz Cincio, and Patrick J. Coles. ``Challenges and opportunities in quantum machine learning''.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

An access model for quantum encoded data

Tags

Source Information