pith. sign in

arxiv: 2303.12834 · v1 · submitted 2023-03-22 · 🪐 quant-ph · cs.AI· cs.LG· stat.ML

The power and limitations of learning quantum dynamics incoherently

Sofiene Jerbi , Joe Gibbs , Manuel S. Rudolph , Matthias C. Caro , Patrick J. Coles , Hsin-Yuan Huang , Zo\"e Holmes This is my paper

Pith reviewed 2026-05-24 10:06 UTC · model grok-4.3

classification 🪐 quant-ph cs.AIcs.LGstat.ML
keywords quantum process learningincoherent learningunitary learningsample complexityquantum dynamicsshallow circuitsquantum entanglementquantum computing
0
0 comments X

The pith

Any efficiently representable unitary can be learned incoherently with arbitrary measurements, but only low-entangling ones with shallow measurements.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper establishes bounds on the sample complexity of learning unitary quantum processes in an incoherent setting where the learner and target do not share quantum information directly. Such a framework matters because it could allow quantum processes to be transferred between different physical hardware platforms without requiring technically difficult entanglement. The authors prove that arbitrary measurements suffice for efficient learning of any efficiently representable unitary by emulating known coherent strategies, while restricting to shallow-depth measurements limits success to low-entangling unitaries. They give an explicit algorithm for the latter case and test it experimentally.

Core claim

If arbitrary measurements are allowed, then any efficiently representable unitary can be efficiently learned within the incoherent framework; however, when restricted to shallow-depth measurements only low-entangling unitaries can be learned. This follows from analyzing the number of measurements required to emulate well-established coherent learning strategies and translating those into sample-complexity bounds for the incoherent case.

What carries the argument

Emulation of coherent learning strategies via sequences of incoherent measurements, which converts measurement counts into sample-complexity bounds.

If this is right

  • Any efficiently representable unitary is learnable incoherently once arbitrary measurements are permitted.
  • Shallow-depth measurements suffice only for low-entangling unitaries.
  • The derived algorithm learns a 16-qubit low-entangling unitary on superconducting hardware.
  • Numerical scaling experiments confirm the approach remains practical for larger low-entangling cases.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Incoherent learning could enable direct transpilation of quantum processes between incompatible hardware platforms.
  • Determining the precise measurement-depth threshold separating low- from high-entangling learnability would sharpen the practical boundary.
  • The same emulation technique might extend to learning other classes of quantum channels or states incoherently.

Load-bearing premise

The number of measurements needed to emulate a coherent strategy can be directly converted into a sample-complexity bound for incoherent learning.

What would settle it

An explicit construction showing that some efficiently representable high-entangling unitary requires superpolynomial incoherent measurements even when arbitrary measurements are permitted.

Figures

Figures reproduced from arXiv: 2303.12834 by Hsin-Yuan Huang, Joe Gibbs, Manuel S. Rudolph, Matthias C. Caro, Patrick J. Coles, Sofiene Jerbi, Zo\"e Holmes.

Figure 1
Figure 1. Figure 1: FIG. 1 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: and further detailed in Appendix B 2 b. Thus, we show that the following theorem holds. Theorem 2 (Power of incoherent learning with shal￾low measurements (informal)). For any low entangling n￾qubit unitary U, that is a unitary that transforms 1-local operators into O(log(n))-local operators, at most poly(n) calls to U are required to incoherently train a parameter￾ized unitary V (θ) to achieve 1/ poly(n) … view at source ↗
Figure 3
Figure 3. Figure 3: a) shows the training loss decreasing as the L-BFGS optimizer [43] minimises the cost function, Fig. 3b) shows the corresponding testing loss decreas￾ing and Fig. 3c) shows the final testing error as a func￾tion of shadow size. The differed sized shadows used here are created from randomly chosen subsets of the full 280000 sample shadow originally collected on the quan￾tum computer. For small shadow sizes … view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4 [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
read the original abstract

Quantum process learning is emerging as an important tool to study quantum systems. While studied extensively in coherent frameworks, where the target and model system can share quantum information, less attention has been paid to whether the dynamics of quantum systems can be learned without the system and target directly interacting. Such incoherent frameworks are practically appealing since they open up methods of transpiling quantum processes between the different physical platforms without the need for technically challenging hybrid entanglement schemes. Here we provide bounds on the sample complexity of learning unitary processes incoherently by analyzing the number of measurements that are required to emulate well-established coherent learning strategies. We prove that if arbitrary measurements are allowed, then any efficiently representable unitary can be efficiently learned within the incoherent framework; however, when restricted to shallow-depth measurements only low-entangling unitaries can be learned. We demonstrate our incoherent learning algorithm for low entangling unitaries by successfully learning a 16-qubit unitary on \texttt{ibmq\_kolkata}, and further demonstrate the scalabilty of our proposed algorithm through extensive numerical experiments.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper derives sample-complexity bounds for incoherent learning of unitary processes by counting the measurements needed to emulate known coherent strategies. It claims that arbitrary measurements suffice for efficient learning of any efficiently representable unitary, while shallow-depth measurements restrict learning to low-entangling unitaries. The work includes a hardware demonstration of the algorithm on a 16-qubit unitary executed on ibmq_kolkata together with numerical scalability tests.

Significance. If the emulation overhead is shown to remain polynomial, the results would clarify the separation between coherent and incoherent process learning and supply a concrete route for platform-independent process transpilation. The 16-qubit hardware run and the explicit numerical experiments constitute concrete strengths that anchor the theoretical claims.

major comments (2)
  1. [analysis of emulating coherent learning strategies (main results / proofs section)] The central positive claim (arbitrary measurements allow efficient learning of any efficiently representable unitary) rests on translating coherent sample complexity into an incoherent experiment count. The manuscript must supply an explicit reduction establishing that the total number of incoherent measurements is at most poly(n,1/ε) times the coherent complexity; without this bound the efficiency statement is not yet supported.
  2. [shallow-depth measurement analysis] The negative result (shallow-depth measurements learn only low-entangling unitaries) uses the same emulation counting argument. If the overhead analysis is incomplete for the arbitrary-measurement case, the shallow-depth limitation claim is likewise load-bearing and requires the same explicit polynomial bound.
minor comments (2)
  1. [Abstract] The abstract states that proofs exist but does not indicate the precise complexity measure (e.g., whether the incoherent bound is stated in terms of number of experiments or total shots).
  2. [Hardware demonstration] In the hardware demonstration paragraph, specify the circuit depth, entanglement measure, and error-mitigation protocol used for the 16-qubit experiment.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading, positive assessment of the hardware demonstration and numerical experiments, and for highlighting the need for greater clarity on the emulation overhead. We address the two major comments below by agreeing to strengthen the explicit reduction in the revised manuscript.

read point-by-point responses

  1. Referee: [analysis of emulating coherent learning strategies (main results / proofs section)] The central positive claim (arbitrary measurements allow efficient learning of any efficiently representable unitary) rests on translating coherent sample complexity into an incoherent experiment count. The manuscript must supply an explicit reduction establishing that the total number of incoherent measurements is at most poly(n,1/ε) times the coherent complexity; without this bound the efficiency statement is not yet supported.

    Authors: We agree that an explicit reduction is required for full rigor. In the revised manuscript we will insert a dedicated subsection (in the proofs section) that spells out the emulation: each coherent measurement is replaced by an incoherent estimation of the corresponding expectation value via repeated preparation and measurement. Using standard median-of-means or Hoeffding bounds, we show that O(poly(n,1/ε)) incoherent shots suffice to achieve the additive error needed for the coherent sample-complexity bound to carry over, yielding an overall polynomial overhead. This directly supports the efficiency claim for arbitrary measurements. revision: yes

  2. Referee: [shallow-depth measurement analysis] The negative result (shallow-depth measurements learn only low-entangling unitaries) uses the same emulation counting argument. If the overhead analysis is incomplete for the arbitrary-measurement case, the shallow-depth limitation claim is likewise load-bearing and requires the same explicit polynomial bound.

    Authors: Because the shallow-depth negative result is proved by the same emulation counting technique, the explicit polynomial overhead bound we will add for the arbitrary-measurement case will apply verbatim to the shallow-depth setting. In the revision we will cross-reference the new subsection so that the limitation to low-entangling unitaries is shown to hold after accounting for the overhead. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper derives its sample-complexity bounds for incoherent unitary learning by explicitly analyzing the number of measurements needed to emulate established coherent strategies, as described in the abstract. This constitutes an independent reduction from coherent to incoherent settings rather than any definitional loop, fitted-input renaming, or load-bearing self-citation chain. No equations or claims reduce a prediction to its own inputs by construction, and the positive result for arbitrary measurements and the negative result for shallow-depth measurements both rest on this measurement-counting analysis, which is self-contained against external coherent-learning benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based on abstract only; no free parameters, axioms, or invented entities are explicitly described in the provided text.

pith-pipeline@v0.9.0 · 5738 in / 1045 out tokens · 20115 ms · 2026-05-24T10:06:51.354356+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On the coherent extension of some Fano-type learning bounds

    quant-ph 2024-04 unverdicted novelty 5.0

    Extends Fano bounds to sufficiency of low conditional entropy and defines a quantum entanglement task for infinite-dimensional systems with bounds via maximal singlet fraction of finite-dimensional approximations.

Reference graph

Works this paper leans on

58 extracted references · 58 canonical work pages · cited by 1 Pith paper · 1 internal anchor

  1. [1]

    Cost concentration results allow us to consider a local version of the training loss. 3. For shallow-depth ans¨ atze V (θ) (e.g., depth O(log(n))), the observables appearing in the training loss remain local ( k∈O (log(n))), and therefore Pauli shadow allow to efficiently simulate this training loss incoherently. sidering observables of the form V (θ)|ψ(i)⟩...

    work page

  2. [2]

    Bisio, G

    A. Bisio, G. Chiribella, G. M. D’Ariano, S. Facchini, and P. Perinotti, Optimal quantum learning of a unitary transformation, Physical Review A 81, 032324 (2010)

    work page 2010

  3. [3]

    Poland, K

    K. Poland, K. Beer, and T. J. Osborne, No free lunch for quantum machine learning, arXiv preprint arXiv:2003.14103 (2020)

    work page arXiv 2003

  4. [4]

    Sharma, M

    K. Sharma, M. Cerezo, Z. Holmes, L. Cincio, A. Sorn- borger, and P. J. Coles, Reformulation of the no-free- lunch theorem for entangled datasets, Physical Review Letters 128, 070501 (2022)

    work page 2022

  5. [5]

    Khatri, R

    S. Khatri, R. LaRose, A. Poremba, L. Cincio, A. T. Sorn- borger, and P. J. Coles, Quantum-assisted quantum com- piling, Quantum 3, 140 (2019)

    work page 2019

  6. [6]

    Jones and S

    T. Jones and S. C. Benjamin, Robust quantum compi- lation and circuit optimisation via energy minimisation, Quantum 6, 628 (2022)

    work page 2022

  7. [7]

    K. Heya, Y. Suzuki, Y. Nakamura, and K. Fujii, Variational quantum gate optimization, arXiv preprint arXiv:1810.12745 (2018)

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  8. [8]

    Cirstoiu, Z

    C. Cirstoiu, Z. Holmes, J. Iosue, L. Cincio, P. J. Coles, and A. Sornborger, Variational fast forwarding for quan- tum simulation beyond the coherence time, npj Quantum Information 6, 1 (2020)

    work page 2020

  9. [9]

    Gibbs, K

    J. Gibbs, K. Gili, Z. Holmes, B. Commeau, A. Arrasmith, L. Cincio, P. J. Coles, and A. Sornborger, Long-time sim- ulations with high fidelity on quantum hardware, arXiv preprint arXiv:2102.04313 (2021)

    work page arXiv 2021

  10. [10]

    Gibbs, Z

    J. Gibbs, Z. Holmes, M. C. Caro, N. Ezzell, H.-Y. Huang, L. Cincio, A. T. Sornborger, and P. J. Coles, Dynamical simulation via quantum machine learning with provable generalization, arXiv preprint arXiv:2204.10269 (2022)

    work page arXiv 2022

  11. [11]

    Huang, R

    H.-Y. Huang, R. Kueng, and J. Preskill, Information- theoretic bounds on quantum advantage in machine learning, Phys. Rev. Lett. 126, 190505 (2021)

    work page 2021

  12. [12]

    Huang, M

    H.-Y. Huang, M. Broughton, J. Cotler, S. Chen, J. Li, M. Mohseni, H. Neven, R. Babbush, R. Kueng, J. Preskill, and J. R. McClean, Quantum advantage in learning from experiments, Science 376, 1182 (2022)

    work page 2022

  13. [13]

    M. C. Caro, H.-Y. Huang, M. Cerezo, K. Sharma, A. Sornborger, L. Cincio, and P. J. Coles, Generalization in quantum machine learning from few training data, Na- ture Communications 13, 4919 (2022)

    work page 2022

  14. [14]

    M. C. Caro, H.-Y. Huang, N. Ezzell, J. Gibbs, A. T. Sornborger, L. Cincio, P. J. Coles, and Z. Holmes, Out- of-distribution generalization for learning quantum dy- namics, arXiv preprint arXiv:2204.10268 (2022)

    work page arXiv 2022

  15. [15]

    Huang, S

    H.-Y. Huang, S. Chen, and J. Preskill, Learning to predict arbitrary quantum processes, arXiv preprint arXiv:2210.14894 (2022)

    work page arXiv 2022

  16. [16]

    M. C. Caro, Learning quantum processes and Hamil- tonians via the Pauli transfer matrix, arXiv preprint arXiv:2212.04471 (2022)

    work page arXiv 2022

  17. [17]

    Y. Mao, M. Gong, K. Nemoto, W. J. Munro, and J. Ma- jer, Perspective on witnessing entanglement in hybrid quantum systems, Applied Physics Letters 119, 110501 (2021)

    work page 2021

  18. [18]

    Waks and C

    E. Waks and C. Monroe, Protocol for hybrid entangle- ment between a trapped atom and a quantum dot, Phys. Rev. A 80, 062330 (2009)

    work page 2009

  19. [19]

    Eichler, C

    C. Eichler, C. Lang, J. M. Fink, J. Govenius, S. Fil- ipp, and A. Wallraff, Observation of entanglement be- tween itinerant microwave photons and a superconduct- ing qubit, Phys. Rev. Lett. 109, 240501 (2012)

    work page 2012

  20. [20]

    Stute, B

    A. Stute, B. Casabone, P. Schindler, T. Monz, P. O. Schmidt, B. Brandst¨ atter, T. E. Northup, and R. Blatt, Tunable ion–photon entanglement in an optical cavity, Nature 485, 482 (2012)

    work page 2012

  21. [21]

    A. N. Craddock, J. Hannegan, D. P. Ornelas-Huerta, J. D. Siverns, A. J. Hachtel, E. A. Goldschmidt, J. V. Porto, Q. Quraishi, and S. L. Rolston, Quantum inter- ference between photons from an atomic ensemble and a remote atomic ion, Phys. Rev. Lett. 123, 213601 (2019)

    work page 2019

  22. [22]

    Scarlino, D

    P. Scarlino, D. J. Van Woerkom, U. C. Mendes, J. V. Koski, A. J. Landig, C. K. Andersen, S. Gasparinetti, C. Reichl, W. Wegscheider, K. Ensslin, et al. , Coherent microwave-photon-mediated coupling between a semi- conductor and a superconducting qubit, Nature Commu- nications 10, 3011 (2019)

    work page 2019

  23. [23]

    Vidal, Efficient classical simulation of slightly entan- gled quantum computations, Phys

    G. Vidal, Efficient classical simulation of slightly entan- gled quantum computations, Phys. Rev. Lett. 91, 147902 (2003)

    work page 2003

  24. [24]

    Or´ us, A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Annals of Physics 349, 117 (2014)

    R. Or´ us, A practical introduction to tensor networks: Matrix product states and projected entangled pair states, Annals of Physics 349, 117 (2014)

    work page 2014

  25. [25]

    Anshu, Z

    A. Anshu, Z. Landau, and Y. Liu, Distributed quantum inner product estimation, in Proceedings of the 54th An- nual ACM SIGACT Symposium on Theory of Computing (2022) pp. 44–51

    work page 2022

  26. [26]

    J. Wang, S. Paesani, R. Santagati, S. Knauer, A. A. Gen- tile, N. Wiebe, M. Petruzzella, J. L. O’Brien, J. G. Rarity, A. Laing, and M. G. Thompson, Experimental quantum Hamiltonian learning, Nature Physics 13, 551 (2017)

    work page 2017

  27. [27]

    Wiebe, C

    N. Wiebe, C. Granade, C. Ferrie, and D. Cory, Quantum Hamiltonian learning using imperfect quantum resources, Physical Review A 89, 042314 (2014)

    work page 2014

  28. [28]

    Wiebe, C

    N. Wiebe, C. Granade, C. Ferrie, and D. G. Cory, Hamiltonian learning and certification using quantum re- sources, Physical Review Letters 112, 190501 (2014)

    work page 2014

  29. [29]

    A. A. Gentile, B. Flynn, S. Knauer, N. Wiebe, S. Paesani, C. E. Granade, J. G. Rarity, R. Santagati, and A. Laing, Learning models of quantum systems from experiments, Nature Physics 17, 837 (2021)

    work page 2021

  30. [30]

    Wilde, A

    F. Wilde, A. Kshetrimayum, I. Roth, D. Hangleiter, R. Sweke, and J. Eisert, Scalably learning quantum many-body Hamiltonians from dynamical data, arXiv preprint arXiv:2209.14328 (2022)

    work page arXiv 2022

  31. [31]

    Gebhart, R

    V. Gebhart, R. Santagati, A. A. Gentile, E. Gauger, D. Craig, N. Ares, L. Banchi, F. Marquardt, L. Pezze, and C. Bonato, Learning quantum systems, arXiv preprint arXiv:2207.00298 (2022)

    work page arXiv 2022

  32. [32]

    Stilck Fran¸ ca, L

    D. Stilck Fran¸ ca, L. A. Markovich, V. Dobrovitski, A. H. Werner, and J. Borregaard, Efficient and robust estimation of many-qubit Hamiltonians, arXiv preprint arXiv:2205.09567 (2022)

    work page arXiv 2022

  33. [33]

    J. Haah, R. Kothari, and E. Tang, Optimal learning of quantum Hamiltonians from high-temperature Gibbs states, arXiv preprint arXiv:2108.04842 (2021)

    work page arXiv 2021

  34. [34]

    Anshu, S

    A. Anshu, S. Arunachalam, T. Kuwahara, and M. Soleimanifar, Sample-efficient learning of interacting quantum systems, Nature Physics 17, 931 (2021)

    work page 2021

  35. [35]

    Fanizza, Y

    M. Fanizza, Y. Quek, and M. Rosati, Learning quan- tum processes without input control, arXiv preprint 8 arXiv:2211.05005 (2022)

    work page arXiv 2022

  36. [36]

    Huang, R

    H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measure- ments, Nature Physics 16, 1050 (2020)

    work page 2020

  37. [37]

    Elben, S

    A. Elben, S. T. Flammia, H.-Y. Huang, R. Kueng, J. Preskill, B. Vermersch, and P. Zoller, The ran- domized measurement toolbox, Nature Review Physics 10.1038/s42254-022-00535-2 (2022)

    work page doi:10.1038/s42254-022-00535-2 2022

  38. [39]

    [13], but the argument was not formalized and its implications for incoherent learning were not appreciated

    1, We note that a similar argument was made in passing in Ref. [13], but the argument was not formalized and its implications for incoherent learning were not appreciated

    work page

  39. [40]

    Maslov and M

    D. Maslov and M. Roetteler, Shorter stabilizer circuits via bruhat decomposition and quantum circuit transfor- mations, IEEE Transactions on Information Theory 64, 4729 (2018)

    work page 2018

  40. [41]

    Schatzki, M

    L. Schatzki, M. Larocca, F. Sauvage, and M. Cerezo, Theoretical guarantees for permutation- equivariant quantum neural networks, arXiv preprint arXiv:2210.09974 (2022)

    work page arXiv 2022

  41. [42]

    S. Chen, J. Cotler, H.-Y. Huang, and J. Li, Exponen- tial separations between learning with and without quan- tum memory, in 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) (IEEE, 2022) pp. 574–585

    work page 2021

  42. [43]

    Aharonov, J

    D. Aharonov, J. Cotler, and X.-L. Qi, Quantum algorith- mic measurement, Nature Communications 13, 1 (2022)

    work page 2022

  43. [44]

    D. C. Liu and J. Nocedal, On the limited memory bfgs method for large scale optimization, Mathematical pro- gramming 45, 503 (1989)

    work page 1989

  44. [45]

    Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018)

    J. Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018)

    work page 2018

  45. [46]

    Mizuta, Y

    K. Mizuta, Y. O. Nakagawa, K. Mitarai, and K. Fujii, Lo- cal variational quantum compilation of large-scale Hamil- tonian dynamics, PRX Quantum 3, 040302 (2022)

    work page 2022

  46. [47]

    Younis, K

    E. Younis, K. Sen, K. Yelick, and C. Iancu, Qfast: Con- flating search and numerical optimization for scalable quantum circuit synthesis, 2021 IEEE International Con- ference on Quantum Computing and Engineering (QCE) , 232 (2021)

    work page 2021

  47. [48]

    Patel, E

    T. Patel, E. Younis, C. Iancu, W. de Jong, and D. Ti- wari, Quest: Systematically approximating quantum cir- cuits for higher output fidelity, Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems AS- PLOS ’22, 514–528 (2022)

    work page 2022

  48. [49]

    Vatan and C

    F. Vatan and C. Williams, Optimal quantum circuits for general two-qubit gates, Physical Review A 69, 032315 (2004)

    work page 2004

  49. [50]

    M. M. Wilde, From classical to quantum shannon theory, arXiv preprint arXiv:1106.1445 (2011)

    work page arXiv 2011

  50. [51]

    Cerezo, A

    M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, Cost function dependent barren plateaus in shal- low parametrized quantum circuits, Nature Communica- tions 12, 1 (2021)

    work page 2021

  51. [52]

    Yu, Assouad, fano, and le cam, Festschrift for Lucien Le Cam: research papers in probability and statistics , 423 (1997)

    B. Yu, Assouad, fano, and le cam, Festschrift for Lucien Le Cam: research papers in probability and statistics , 423 (1997)

    work page 1997

  52. [53]

    StackExchange, Total variation inequality for the product measure

    M. StackExchange, Total variation inequality for the product measure

    work page

  53. [54]

    The power and limitations of learning quantum dynamics incoherently

    D. A. Roberts and B. Yoshida, Chaos and complexity by design, Journal of High Energy Physics2017, 121 (2017). 1 Supplementary Material for “The power and limitations of learning quantum dynamics incoherently” Appendix A: Preliminaries We consider a unitary compilation scenario where the training data about the target unitary U is not given coherently as{|...

    work page 2017

  54. [55]

    simulate

    Summary of the algorithms In order to learn a target unitary U, the parametrized ansatz V (θ) is trained via optimization of a training loss that is representative of the overlap between U and V (θ). For reasons explained below, we consider different training losses for the incoherent setting using deep measurements and the setting using shallow measuremen...

    work page

  55. [56]

    estimation j fails

    Sample complexity analysis We divide the analysis of the sample complexity of our incoherent learning protocols into two stages: (i) we analyze the sample complexity to incoherently estimate the training loss C(θ), via the algorithms described above, for any sequence of parameter settings θ(1), . . . ,θ(L), and (ii) we show how this ability to estimate th...

    work page

  56. [57]

    GHZ-like

    Remarks on the computational complexity So far, we’ve only discussed the sample complexity of our incoherent learning protocols. In this section, we point out the caveats that appear when looking at their computational complexity. The most obvious caveat of both protocols has to do with the exhaustive search used in both Theorem B.1 and Theorem B.2. While...

    work page

  57. [58]

    Lemma C.1

    W arm-up example We start by studying the simpler case where the shallow measurements considered are limited to be random Pauli measurements, as those used in Pauli shadows. Lemma C.1. Consider the product-POVM F = 1 3n{|0⟩⟨0|,|1⟩⟨1|,|+⟩⟨+|,|−⟩⟨−|,|i⟩⟨i|,|− i⟩⟨−i|}⊗n which corresponds to measuring in the eigenbasis of a random n-qubit Pauli observable in ...

    work page

  58. [59]

    GHZ-like

    General case We now move to the general setting of arbitrary product measurements, that are moreover allowed to be adaptively chosen (i.e., the next input state and measurement basis can be chosen as a function of previous measurement outcomes). Theorem C.1. Call F1, . . . , FT an arbitrary sequence of n-qubit product-POVMs, i.e., Fi ={wi,j2n|φi,j⟩⟨φi,j|}...

    work page