Learning the Complexity of Weakly Noisy Quantum States

Comment 1: Could the authors elaborate on specific quantum hardware requirements for implementing the algorithm? Are there particular quantum systems where the algorithm's performance has been or can be practically tested?

Response: We thank the reviewer for this comment. We note that our learning algorithm has very few limitations to the practical quantum hardware. In the Alg.~1, we only require (i) the target weakly noisy quantum state $\rho_{\rm un}$, and (ii) the QCA state set $\hat{\rho}_{\rm QCA}$, which is essentially the classical shadow representation [Hsin-Yuan Huang et al., 2020]. When preparing the classical shadow, recent work has successfully integrated quantum error mitigation methods into the classical shadow protocol, providing rigorous theoretical guarantees in preparing shadows even in noisy environments [Hamza Jnane et al., 2024]. As a result, our Alg 1 only requires a quantum computer which supports the quantum error mitigation function, with approximately $50-100$ noisy qubits and $\geq 0.99$ quantum gate fidelity. Some popular quantum computation platforms may satisfy these requirements and can be used to prepare the required classical shadow, such as Eagle used in Ref. [Youngseok Kim et al., 2023] and Sycamore [Frank Arute et al., 2019]. This work is essentially a theoretical research, and the algorithm has not yet been explicitly tested on these practical platforms. In the future work, we are happy to explore how the algorithm performs on practical quantum hardware, which remains a key direction for further validation.

References: Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16(10):1050–1057, 2020.

Hamza Jnane, Jonathan Steinberg, Zhenyu Cai, H Chau Nguyen, and B´alint Koczor. Quantum error mitigated classical shadows. PRX Quantum, 5(1):010324, 2024.

Youngseok Kim, Andrew Eddins, Sajant Anand, KenXuan Wei, Ewout van den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, and Abhinav Kandala. Evidence for the utility of quantum computing before fault tolerance. Nature, 618:500–505, 2023.

Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505–510, 2019.

Comment 2: How does the algorithm perform under different types of quantum noise models? Is the accuracy in the complexity predictions different between, e.g., local-depolarizing versus global-depolarizing channels?

Response: We thank the reviewer for this interesting question. From a theoretical perspective, our algorithm is broadly applicable to a wide range of noise models where the local noise channel can be decomposed using a set of Kraus operators, and the noise strength is approximately $p=\mathcal{O}(n^{-1})$ as stated in Fact 1. Moreover, the theoretical guarantees provided by Theorems 1 and 2 impose no additional constraints on the noise model. We also note that the global depolarizing channel is essentially a special case of contracting $n$ local noise models. Specifically, given the global depolarizing channel $\mathcal{E}$ with noisy strength $p_g$ and local depolarizing channel

$\otimes_j\mathcal{E}_j$ with strength $p_l$,

according to the relative entropy inequality, for any input state $\rho$, we can observe the relationships

$

D(\mathcal{E}(\rho)\|I_n/2^n)\leq (1-p_g)D(\rho\|I_n/2^n),

$

and

$

D(\otimes_{j=1}^n\mathcal{E}_j(\rho)\|I_n/2^n)\leq (1-p_l)^nD(\rho\|I_n/2^n)

$

hold. These inequalities indicate that the global depolarizing channel is much weaker than local noise, given the same noise strength. Consequently, for the global depolarizing channel, our algorithm is capable of handling scenarios where $p_g\leq\mathcal{O}(1)$, while maintaining comparable prediction accuracy. This suggests that the algorithm can effectively handle both types of noise, with only a minor difference in performance under different noise strengths. We have included this detailed discussion in the revised manuscript on Pages 16-17.

Comment 3: The paper should include a more detailed discussion of the computational and practical limitations of the algorithm (for example, stress-testing the algorithm under increased complexities and reporting on its degradation or stability performance.

Response: Thank you for this insightful comment. We will include following discussions to the revised manuscript.

Theoretical Guarantee: The time complexity and sample complexity of our algorithm are rigorously derived in Theorems 2 and 3, both of which depend polynomially on the number of qubits of the target quantum state. These results imply that our learning algorithm remains efficient even as the complexity of the input states increases.

Numerical Simulation: we supplemented the stress testing of the proposed quantum learning algorithm in this study. Specifically, we applied the algorithm to estimate the complexity lower bound of quantum states under noisy environments for one-dimensional dynamical evolution. We tested the transverse-field Ising model with system sizes of $1\times 6$, $1\times 8$, and $1\times 10$, and the numerical results are presented in Figure 3. Our findings indicate that the complexity lower bound of noisy quantum circuits does not grow linearly with circuit depth, which is consistent to the results given by Figure 1 in the main file.

Furthermore, we observed that as the system size and complexity increase, the curves corresponding to two different quantum states, $\tilde{R}=2$ and $\tilde{R}=10$, exhibit similar overall trends for the system size $n\in\{6, 8, 10\}$. Moreover, the variance of the algorithm does not increase with the growing system size but remains consistently stable. At the same time, the gap between the curves of quantum states with different complexities does not show a closing trend as the system size grows. These characteristics demonstrate the robustness of our learning algorithm against increases in system size and complexity. Therefore, our algorithm remains reliable for predicting the complexity of large-scale weakly noisy quantum states. Please refer to Appendix L on Pages 28-19.

Comment 4: Incorporating key proofs and insights from the appendices into the main body would enhance the paper's value, as some essential concepts, like the subroutine BMaxS, are only briefly mentioned in the main text. It would also be very useful if the manuscript provided a framework for empirical testing and validation of the algorithm, including benchmark selection and metrics of validation. This would help bridge the missing gap between theoretical research and practical applications and give a much stronger justification for the effectiveness of the algorithm in noisy quantum environments.

Response: We thank the reviewer for their valuable comment. In response, we have clarified several related concepts in the revised manuscript. Due to the 10-page limit for the main text, most of the details about the BMaxS algorithm are provided in the supplementary material, but we have made every effort to explain the key aspects of the algorithm within the main text. Additionally, we have included a numerical simulation in the revised manuscript to analyze the Hamiltonian dynamics from Ref.[Youngseok Kim et al., 2023] and benchmark the complexity of noisy Hamiltonian dynamics. Our simulations are capable of testing the algorithm on up to a 12-qubit density matrix, which corresponds to the complexity of a 24-qubit state vector. Please refer to Page 7 for explaining BMaxS, and Pages 8-9 and Pages 28-29 for supplemented numerical simulation results.

Youngseok Kim, Andrew Eddins, Sajant Anand, KenXuan Wei, Ewout van den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, and Abhinav Kandala. Evidence for the utility of quantum computing before fault tolerance. Nature, 618:500–505, 2023.

We thank the reviewer for their insightful comments and suggestions. In response, we have clarified the quantum hardware requirements of our learning algorithm and highlighted its robustness under both local and global noise channels. To validate the practical applicability of our algorithm, we conducted numerical simulations and stress tests. The results successfully demonstrate that the complexity of weakly noisy quantum states exhibits a fundamentally different trend compared to that of pure random quantum states, thereby broadening the understanding of quantum state complexity in the regime of weak noise. We hope these revisions and clarifications address your concerns and improve the clarity of our arguments. We trust that these changes will help in reassessing the evaluation of our work.

Dear Reviewer wYLf,

Thanks agian for your constructive suggestions. We have made our best effort to address your comments and revised the manuscript accordingly. As the public discussion period is nearing its end, we would be delighted to hear your feedback and suggestions on our latest responses. We look forward to your reply.

Best regards!

Comment 2: Given that quantum noise can accumulate rapidly in depth significantly in each quantum system, how does your proposed learning approach remain feasible in practice? Why gate-independent noise channel? Please clarify the practicality of your noise model and its implications for the scalability of your method. Better to compare with an explicit circuit model example.

Response: We thank the reviewer for these comments. In the proposed learning approach (Alg~1), the algorithm requires (i) the target weakly noisy quantum state $\rho_{\rm un}$, and (ii) the QCA state set $\hat{\rho}_{QCA}$.

The target weakly noisy state naturally contains noise signals, while the QCA state set $\hat{\rho}_{\rm QCA}$ is provided by the classical shadow representation [H. Huang et al., 2020]. When preparing the classical shadow, recent result successfully embedded the quantum error mitigation method into the classical shadow protocol, which provides rigorous theoretical guarantees even in the noisy environment [H. Jnane et al., 2024].

In quantum computing research, the gate-independent noise model assumes that the noise affecting quantum operations is uniform across all gates, regardless of their type or implementation. This simplification is widely adopted for several reasons:

Theoretical Simplification: Assuming gate-independent noise allows researchers to develop and analyze error correction protocols and fault-tolerant methods without delving into the complexities introduced by gate-specific noise characteristics [E. Knill et al., 2008, J. Helsen et al., 2019, J. Claes et al., 2021, S. Chen et al., 2021]. This uniformity facilitates the derivation of general results and theoretical bounds [M. A Nielsen et al., 2001].

Practical Approximations: In certain quantum systems, particularly those with well-calibrated gates operating on the same number of qubits and utilizing uniform control mechanisms, noise variations across different gates can be negligible [P. W. Shor, 1996, F. Arute et al., 2019]. In such cases, the gate-independent noise model serves as a reasonable approximation, streamlining analysis without significantly compromising accuracy.

Alignment with Twirled Noise Models: Techniques like Pauli twirling are employed to transform complex noise channels into diagonal forms on the Pauli basis [J. Wallman et al., 2016]. While twirling simplifies the noise structure, it does not inherently eliminate gate dependence. However, in many scenarios, the resulting noise can be approximated as gate-independent, aligning with the assumptions of the model.

The gate-independent noise model provides a foundational framework for understanding error propagation and developing correction strategies, which is a useful abstraction for theoretical exploration and the initial development of error correction methods. We leave an open question of how to depict the gate-dependent noise, which usually happens in larger, more complex quantum architectures. We have supplemented above discussions to Page 16. For explicit circuit model example, please refer to Sec. 6 on Page 9.

References:

Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics, 16(10):1050–1057, 2020.

Hamza Jnane, Jonathan Steinberg, Zhenyu Cai, H Chau Nguyen, and B´alint Koczor. Quantum error mitigated classical shadows. PRX Quantum, 5(1):010324, 2024.

Emanuel Knill, Dietrich Leibfried, Rolf Reichle, Joe Britton, R Brad Blakestad, John D Jost, Chris Langer, Roee Ozeri, Signe Seidelin, and David J Wineland. Randomized benchmarking of quantum gates. Physical Review A, 77(1):012307, 2008.

Jonas Helsen, Xiao Xue, Lieven MK Vandersypen, and Stephanie Wehner. A new class of efficient random- ized benchmarking protocols. npj Quantum Information, 5(1):1–9, 2019.

Jahan Claes, Eleanor Rieffel, and Zhihui Wang. Character randomized benchmarking for non-multiplicity- free groups with applications to subspace, leakage, and matchgate randomized benchmarking. PRX Quan- tum, 2(1):010351, 2021.

Senrui Chen, Wenjun Yu, Pei Zeng, and Steven T. Flammia. Robust shadow estimation. PRX Quantum, 2:030348, Sep 2021.

Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information, volume 2. Cam- bridge university press Cambridge, 2001.

Peter W Shor. Fault-tolerant quantum computation. In Proceedings of 37th conference on foundations of computer science, pages 56–65. IEEE, 1996.

Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505–510, 2019.

Joel J Wallman and Joseph Emerson. Noise tailoring for scalable quantum computation via randomized compiling. Physical Review A, 94(5):052325, 2016.

Comment 1: Could you provide a more compelling motivation for studying weakly noisy quantum states? How do they relate to real-world quantum systems, and what are the potential applications of your findings?

Response: Thanks for this valuable suggestion. In our paper, weakly noisy quantum states refer to quantum states with $\mathcal{O}(\log n)$ depth, where each quantum gate is affected by a $p=\mathcal{O}(n^{-1})$-strength noise channel. We note that weakly noisy quantum states are ubiquitous in the real world. For example, in the current Noisy Intermediate-Scale Quantum (NISQ) era, quantum computers generally have $\leq 10^{3}$ qubits, and the noise strength of single- and double-qubit gates is generally $10^{-3}$. Due to the limited coherent time of quantum devices, NISQ quantum computers can only process shallow (constant or logarithmic) depth quantum circuits. As a result, all quantum states prepared by near-term quantum computers can be recognized as weakly noisy quantum states.

Understanding the complexity of weakly noisy states have several significant applications. Firstly, the predicted complexity enables the classification of the target unknown state $\rho_{\rm un}$ into one of the following scenarios: (i) $\rho_{\rm un}$ can be approximated by an estimator generated by constant-depth noiseless circuits, which is amenable to classical simulation as shown in [J. C. Napp et al., 2022, S. Bravyi et al., 2021], (ii) $\rho_{\rm un}$ can be approximated using noiseless circuits with sub-logarithmic depth, a task that may present classical computational challenges, as discussed in [A. Deshpande et al., 2022], and (iii) $\rho_{\rm un}$ cannot be approximated by any linear combination of circuits constrained to a specific architecture with a depth of at most $\log n$. Besides benchmarking the NISQ computational power (whether its output can be classically simulated), the proposed quantum algorithm and predicted weakly noisy state complexity may have practical applications in various fields, including understanding the black hole theory and the quantum phase transition. For example, in the context of the Anti-de-Sitter-space/Conformal Field Theory (AdS/CFT) correspondence, the ``complexity equals volume'' conjecture [D. Stanford et al., 2014] suggests that the boundary state of the correspondence has a complexity proportional to the volume behind the event horizon of a black hole in the bulk geometry. However, when measuring the boundary state, the interaction with the surrounding environment inevitably introduces a noise signal, making the pure state noisy. Furthermore, in quantum many-body systems, quantum phase transitions occur when the external parameters varies [S. Sachdev 1999], and the ability to correctly predict the quantum phase transition boundary can help us understand many strong-correlated systems [B. Zheng et al., 2017]. It is known that quantum topological phases can be distinguished by their ground state complexity [Y. Huang et al., 2015], and the shadow tomography [H. Huang et al., 2022] method utilized quantum channels to provide a noisy state approximation to the ground state. Predicting complexity of such noisy ground state approximations may recognize the topological phases of matter. We have supplemented above discussions in the revised manuscript on Page~2.

References:

John C Napp, Rolando L La Placa, Alexander M Dalzell, Fernando GSL Brandao, and Aram W Harrow. Efficient classical simulation of random shallow 2d quantum circuits. Physical Review X, 12(2):021021, 2022.

Sergey Bravyi, David Gosset, and Ramis Movassagh. Classical algorithms for quantum mean values. Nature Physics, 17(3):337–341, 2021.

Abhinav Deshpande, Pradeep Niroula, Oles Shtanko, Alexey V Gorshkov, Bill Fefferman, and Michael J Gullans. Tight bounds on the convergence of noisy random circuits to the uniform distribution. PRX Quantum, 3(4):040329, 2022.

Douglas Stanford and Leonard Susskind. Complexity and shock wave geometries. Physical Review D, 90(12):126007, 2014.

Subir Sachdev. Quantum phase transitions. Physics World, 12(4):33, 1999.

Bo-Xiao Zheng, Chia-Min Chung, Philippe Corboz, Georg Ehlers, Ming-Pu Qin, Reinhard M Noack, Hao Shi, Steven R White, Shiwei Zhang, and Garnet Kin-Lic Chan. Stripe order in the underdoped region of the two-dimensional hubbard model. Science, 358(6367):1155–1160, 2017.

Yichen Huang, Xie Chen, et al. Quantum circuit complexity of one-dimensional topological phases. Physical Review B, 91(19):195143, 2015.

Hsin-Yuan Huang, Richard Kueng, Giacomo Torlai, Victor V Albert, and John Preskill. Provably efficient machine learning for quantum many-body problems. Science, 377(6613):eabk3333, 2022.

Dear Reviewer eyDN,

Thanks agian for your constructive suggestions. We have made our best effort to address your comments and revised the manuscript accordingly. As the public discussion period is nearing its end, we would be delighted to hear your feedback and suggestions on our latest responses. We look forward to your reply.

Best regards!

Comment 3: The paper focuses on weakly noisy states with specific noise parameters (O(1/n) strength and O(poly log n) depth). Could the authors comment on whether similar techniques could be extended to more general noise models or stronger noise regimes? If not, could the authors describe if stronger results are simply impossible for any learning algorithm?

Response: We appreciate the reviewer's insightful question.

In Definition 2, we only assume the noise channel can be decomposed by a set of Kraus operators, which is a general noise model in characterizing practical scenarios. We only require that the gate noise strength $p=\mathcal{O}(n^{-1})$ meanwhile the quantum circuit depth is constrained to be $\tilde{R}\leq {\rm poly}\log n$. These two conditions directly lead to Fact 1 and Equation 9 (on Page 5), which suggest that weakly noisy quantum states may have a constant overlap with their corresponding pure state (when $p=0$). This result enables the use of Definition 3 to characterize the complexity of weakly noisy quantum states, as $1-\epsilon$ (as defined in Definition 3) is not expected to be exponentially vanish.

From this perspective, our algorithm may not be well-suited for characterizing state complexity in scenarios where the noise strength is $p=\mathcal{O}(1)$ and circuit depth $\tilde{R}\geq\Omega(\log n)$. However, this does not imply that predicting the complexity of noisy states prepared by deep quantum circuits with constant error strength is inherently hard. According to the result in Ref. [Daniel Stilck Franca et al., 2021], noisy quantum states with $p=\mathcal{O}(1)$ and $\tilde{R}\geq\Omega(\log n)$ are close to the maximally mixed state in terms of trace distance, derived by the relative entropy and Pinsker's inequality. Given this observation, for a noisy quantum state $\rho_{\tilde{R},p}$ with $p=\mathcal{O}(1)$ and $\tilde{R}\geq\Omega(\log n)$, the standard SWAP test can be used to estimate the trace distance between $\rho_{\tilde{R},p}$ and the maximally mixed state. If the trace distance is sufficiently small, then the complexity of $\rho_{\tilde{R},p}$ can be approximately characterized by that of maximally mixed state, which has a constant circuit depth complexity.

Reference: Daniel Stilck Franca and Raul Garcia-Patron. Limitations of optimization algorithms on noisy quantum devices. Nature Physics, 17(11):1221–1227, 2021.

Comment 2: Could the authors provide numerical simulations demonstrating their learning algorithm's performance on concrete examples of noisy quantum states? This would help validate the theoretical guarantees and provide intuition about the practical performance.

Response: We thank the reviewer for this suggestion. We have added a numerical simulation to learn from the Hamiltonian dynamics studied in Ref. [Y. Kim et al., 2023] and benchmark the complexity of noisy Hamiltonian dynamics. Due to limitations in revision time and current computational power, we may numerically test our algorithm on at most a 12-qubit density matrix (equivalent to a 24-qubit state vector), rather than on a 50-qubit density matrix, which is beyond the capabilities of the current classical simulation. We are happy to leave the large-scale algorithm simulation to future work. The numerical simulation has been supplemented to the revised manuscript. Please refer to Sec. 6 on Page 9 and Appendix L. on Page 28.

References:

Youngseok Kim, Andrew Eddins, Sajant Anand, KenXuan Wei, Ewout van den Berg, Sami Rosenblatt, Hasan Nayfeh, Yantao Wu, Michael Zaletel, Kristan Temme, and Abhinav Kandala. Evidence for the utility of quantum computing before fault tolerance. Nature, 618:500–505, 2023.

Finally, we would like to highlight the differences between weakly noisy quantum states and pseudorandom quantum states. Specifically, we consider the second-moment statistic property of a set of pseudorandom quantum circuits $U$ whose circuit depth $\tilde{R}\leq {\rm poly}\log n$. In Ref. [T. Schuster et al., 2024], they claimed that even $\mathcal{O}(\log(n))$-depth Clifford circuits may approximate the unitary 2-design property given by Haar measure. Then, we may suppose $U=U_1\cdots U_{\tilde{R}}$ representing a random Clifford circuit, then for the initial state $|0^n\rangle\langle0^n|$ and arbitrary observable $O$, we have

$

M_2(U)=\int_{U\sim{\rm Cl}(2^n)}{\rm Tr}\left[U|0^n\rangle\langle0^n|U^{\dagger
}O\right]{\rm Tr}\left[U|0^n\rangle\langle0^n|U^{\dagger
}O\right]=\frac{1}{d(d^2-1)}\left[{\rm Tr}^2[O]+{\rm Tr}[O^2]\right].

$

On the other hand, in the context of weakly noisy environment, the Clifford circuit $U$ may transform to the channel representation $\mathcal{U}=\bigcirc_{r=1}^{\tilde R}\mathcal{E}\circ \mathcal{U}_r$ where $\mathcal{E}$ represents a $n$-qubit Pauli channel and $\mathcal{U}_r=U_r(\cdot)U_r^{\dagger}$ represents a layer of Clifford gate.

According to the ``Channel Pushing'' lemma given by Ref [Y. Quek et al., 2024] (Lemma~10), we may rewrite the noisy channel by $\mathcal{U}=\mathcal{E}^{\prime}\circ\bigcirc_{r=1}^{\tilde R}\mathcal{U}_r$,

where $\mathcal{E}^{\prime}$ also represents an $n$-qubit Pauli channel. Let the channel $\mathcal{E}^{\prime}=\sum_lK_l(\cdot)K_l^{\dagger}$, where $K_l$ represents the Kraus operator satisfying $\sum_lK_l^{\dagger}K_l=I$, we have \begin{eqnarray} \begin{split} M_2(\mathcal{U})=&\int_{U\sim{\rm Cl}(2^n)}{\rm Tr}\left[\mathcal{U}(|0^n\rangle\langle0^n|)O\right]{\rm Tr}\left[\mathcal{U}(|0^n\rangle\langle0^n|)O\right] \end{split} \end{eqnarray}

$

=\sum\limits_{l_1,l_2}\int_{U\sim{\rm Cl}(2^n)}{\rm Tr}\left[K_{l_1}U(|0^n\rangle\langle0^n|)U^{\dagger}K_{l_1}^{\dagger}O\right]{\rm Tr}\left[K_{l_2}U(|0^n\rangle\langle0^n|)U^{\dagger}K_{l_2}^{\dagger}O\right]

$

$

=\sum\limits_{l_1,l_2}\left(\frac{1}{d(d^2-1)}\left({\rm Tr}(K_{l_1}OK_{l_1}^{\dagger}){\rm Tr}(K_{l_2}OK_{l_2}^{\dagger})+{\rm Tr}(K_{l_1}OK_{l_1}^{\dagger}K_{l_2}OK_{l_2}^{\dagger})\right)\right).

$

We note that the interaction term $\sum_{l_1,l_2}{\rm Tr}(K_{l_1}OK_{l_1}^{\dagger}K_{l_2}OK_{l_2}^{\dagger})$ may not equal to ${\rm Tr}(O^2)$, and this leads to $M_2(U)\neq M_2(\mathcal{U})$. This comparison indicates that even if an algorithm can learn the difference between noisy ensembles and Haar-random states, this does not imply that the algorithm can be used to distinguish between pseudorandom ensembles and Haar-random ensembles.

The above discussions demonstrate the fundamental difference between our work and Ref. [T. Schuster et al., 2024]. Such difference implies that the efficiency of our learning algorithm may not contradict the findings presented in Ref. [T. Schuster et al., 2024]. We hope these theoretical examples help clarify your initial confusion. This discussion has been supplemented to the revised manuscript on Pages~15-16.

References: Yihui Quek, Daniel Stilck Fran¸ca, Sumeet Khatri, Johannes Jakob Meyer, and Jens Eisert. Exponentially tighter bounds on limitations of quantum error mitigation. Nature Physics, 20(10):1648–1658, 2024.

Comment 1: It is well known in quantum complexity theory that the circuit complexity of a quantum state cannot be efficiently learned [1, 2, 3]. For example, the existence of pseudorandom states that can be generated in polylog depth on 1D circuits [3] immediately implies that no polynomial-time quantum algorithm can distinguish between polylog circuit complexity (complexity defined in terms minimum circuit depth) and exponential circuit complexity. Hence, it is not possible to predict complexity of a state in polynomial processing time without first solving quantumly hard cryptographic problems. I find it very confusing that the authors claim to predict circuit complexity in polynomial time. Could the authors provide further clarification on how it is possible to predict the circuit complexity of a state in polynomial time? There are a plethora of existing results proving that circuit complexity is not efficiently learnable. Assuming the claims given in this work are correct, could the authors provide a detailed exposition for how this seemingly contradictory statements can be resolved? [1] "Pseudorandom quantum states." Advances in Cryptology–CRYPTO 2018. [2] "Quantum pseudoentanglement." arXiv preprint arXiv:2211.00747 (2022). [3] "Random unitaries in extremely low depth." arXiv preprint arXiv:2407.07754 (2024).

Response: We truly appreciate the reviewer for mentioning very recent work [T. Schuster et al., 2024]. In our paper, we primarily focus on the task of learning specific quantum states using shallow-depth circuits. This approach does not contradict the concept of computational indistinguishability between two quantum random ensembles. To elaborate, a pseudorandom unitary (PRU) refers to a family of efficiently computable quantum circuits that ensure no polynomial-time quantum algorithm can distinguish between a unitary drawn from the PRU family and one sampled from the Haar measure, in other words, learning the difference between two ensembles is quantum hard. In contrast, our learning problem involves reconstructing a given shallow-depth, weakly noisy quantum state by optimizing the a loss function related to the original state and the reconstructed state. Furthermore, recent works [H. Huang et al., 2024, Z. Landau et al., 2024] have also demonstrated that fixed shallow quantum circuits and quantum pure states (including $1$D-$\mathcal{O}(\log n)$-depth and all-to-all $\mathcal{O}(\log\log n)$-depth) can be efficiently learned. These results demonstrate significant differences between scenarios with and without 'randomness'. Compared with [T. Schuster et al., 2024], our work is more similar to Refs.[H. Huang et al., 2024, Z. Landau et al. 2024], which focus on a specific quantum state rather than an ensemble. We also note that the pure state can be classified according to their complexity when the target states exhibit certain physical structures, such as the ground state of XXZ models and the toric code, as studied in Ref.~[H. Huang et al., 2022]

References:

Thomas Schuster, Jonas Haferkamp, and Hsin-Yuan Huang. Random unitaries in extremely low depth. arXiv preprint arXiv:2407.07754, 2024.

Hsin-Yuan Huang, Yunchao Liu, Michael Broughton, Isaac Kim, Anurag Anshu, Zeph Landau, and Jarrod R McClean. Learning shallow quantum circuits. arXiv preprint arXiv:2401.10095, 2024.

Zeph Landau and Yunchao Liu. Learning quantum states prepared by shallow circuits in polynomial time. arXiv preprint arXiv:2410.23618, 2024.

Hsin-Yuan Huang, Richard Kueng, Giacomo Torlai, Victor V Albert, and John Preskill. Provably efficient machine learning for quantum many-body problems. Science, 377(6613):eabk3333, 2022.

Dear Reviewer m7qv,

Thanks agian for your constructive suggestions. We have made our best effort to address your comments and revised the manuscript accordingly. As the public discussion period is nearing its end, we would be delighted to hear your feedback and suggestions on our latest responses. We look forward to your reply.

Best regards!

I would like to thank the authors for their responses. Their responses have addressed my questions.