Quantum advantage is widely expected to require sufficiently deep circuits, where correlations and global computational structure can grow beyond the reach of efficient classical simulation. This expectation is especially stark for constant-depth circuits with local readout: the expectation value of any fixed local observable lies within a bounded backward lightcone and is therefore classically tractable. Here we show that measurement feedback changes this picture. We establish a strict hierarchy of computational power: at fixed coherent depth, increasing the number of feedback outcomes strictly enlarges the class of functions accessible through a local expectation value. The two ends of this hierarchy exhibit distinct computational regimes. With logarithmic feedback, local expectation values for product-state inputs are efficiently classically simulable. Polynomial feedback, by contrast, enables an explicit family of adaptive shallow circuits to encode prime-field discrete logarithm problem~(DLP) into a fixed single-qubit expectation. Assuming the standard worst-case classical hardness of DLP, estimating this expectation value is classically hard. These results reveal a feedback-driven complexity transition, with further implications for resource lower bounds on DLP and the complexity of local-observable estimation under area-law entanglement. Our results open a new route to quantum advantage with shallow quantum circuits.
Yusen Wu, Yukun Zhang, Xiao-Ming Zhang et al.· 0 citations
Quantum reservoir computing (QRC) offers a powerful approach to exploit the rich dynamics of quantum systems for information processing. However, the computational performance of conventional Hermitian reservoirs is inherently constrained by their nonlinearity and information-spreading ability. In this work, we propose a non-Hermitian QRC in which non-Hermitian dynamics are employed as a tunable resource to significantly enhance the QRC performance. By incorporating an imaginary interaction term into the one-dimensional XY spin model, the reservoir's information propagation extends beyond the Lieb-Robinson bound, resulting in accelerated information scrambling. Through spectral analysis and memory evaluation, we demonstrate that the non-Hermitian reservoir can be tuned toward the edge of chaos by varying a single parameter that controls the non-Hermitian strength. This tuning optimizes both memory and computational capacities, which are crucial for processing temporal sequences. For applications, we evaluate the predictive performance of both classical and quantum chaotic time series. Our results demonstrate superior performance compared with the Hermitian counterpart, with particularly notable advantages in predicting signals generated by the Sachdev-Ye-Kitaev model.
Yusen Wu, Chuan Wang, Lufan Zhang et al.· Quantum Science and Technolo...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
