We propose and analyze a novel interactive protocol for demonstrating quantum computational advantage, which is efficiently classically verifiable. Our protocol relies upon the cryptographic hardness of trapdoor claw-free functions (TCFs). Through a
surprising connection to Bells inequality, our protocol avoids the need for an adaptive hardcore bit, with essentially no increase in the quantum circuit complexity and no extra cryptographic assumptions. Crucially, this expands the set of compatible TCFs, and we propose two new constructions: one based upon the decisional Diffie-Hellman problem and the other based upon Rabins function, $x^2 bmod N$. We also describe two unique features of our interactive protocol: (i) it allows one to discard so-called garbage bits, thereby removing the need for reversibility in the quantum circuits, and (ii) there exists a natural post-selection scheme, which significantly reduces the fidelity needed to demonstrate quantum advantage. Finally, we design several efficient circuits for $x^2 bmod N$ and describe a blueprint for their implementation on a Rydberg-atom-based quantum computer.
In [Van Beeumen, et. al, HPC Asia 2020, https://www.doi.org/10.1145/3368474.3368497] a scalable and matrix-free eigensolver was proposed for studying the many-body localization (MBL) transition of two-level quantum spin chain models with nearest-neig
hbor $XX+YY$ interactions plus $Z$ terms. This type of problem is computationally challenging because the vector space dimension grows exponentially with the physical system size, and averaging over different configurations of the random disorder is needed to obtain relevant statistical behavior. For each eigenvalue problem, eigenvalues from different regions of the spectrum and their corresponding eigenvectors need to be computed. Traditionally, the interior eigenstates for a single eigenvalue problem are computed via the shift-and-invert Lanczos algorithm. Due to the extremely high memory footprint of the LU factorizations, this technique is not well suited for large number of spins $L$, e.g., one needs thousands of compute nodes on modern high performance computing infrastructures to go beyond $L = 24$. The matrix-free approach does not suffer from this memory bottleneck, however, its scalability is limited by a computation and communication imbalance. We present a few strategies to reduce this imbalance and to significantly enhance the scalability of the matrix-free eigensolver. To optimize the communication performance, we leverage the consistent space runtime, CSPACER, and show its efficiency in accelerating the MBL irregular communication patterns at scale compared to optimized MPI non-blocking two-sided and one-sided RMA implementation variants. The efficiency and effectiveness of the proposed algorithm is demonstrated by computing eigenstates on a massively parallel many-core high performance computer.
Many-body chaos has emerged as a powerful framework for understanding thermalization in strongly interacting quantum systems. While recent analytic advances have sharpened our intuition for many-body chaos in certain large $N$ theories, it has proven
challenging to develop precise numerical tools capable of exploring this phenomenon in generic Hamiltonians. To this end, we utilize massively parallel, matrix-free Krylov subspace methods to calculate dynamical correlators in the Sachdev-Ye-Kitaev (SYK) model for up to $N = 60$ Majorana fermions. We begin by showing that numerical results for two-point correlation functions agree at high temperatures with dynamical mean field solutions, while at low temperatures finite-size corrections are quantitatively reproduced by the exactly solvable dynamics of near extremal black holes. Motivated by these results, we develop a novel finite-size rescaling procedure for analyzing the growth of out-of-time-order correlators (OTOCs). We verify that this procedure accurately determines the Lyapunov exponent, $lambda$, across a wide range in temperatures, including in the regime where $lambda$ approaches the universal bound, $lambda = 2pi/beta$.
In 2009, Shepherd and Bremner proposed a test of quantum capability arXiv:0809.0847 that is attractive because the quantum machines output can be verified efficiently by classical means. While follow-up papers gave evidence that directly simulating t
he quantum prover is classically hard, the security of the protocol against other (non-simulating) classical attacks has remained an open question. In this paper, I demonstrate that the protocol is not secure against classical provers. I describe a classical algorithm that can not only convince the verifier that the (classical) prover is quantum, but can in fact can extract the secret key underlying a given protocol instance. Furthermore, I show that the algorithm is efficient in practice for problem sizes of hundreds of qubits. Finally, I provide an implementation of the algorithm, and give the secret vector underlying the $25 challenge posted online by the authors of the original paper.
We prove the existence of non-equilibrium phases of matter in the prethermal regime of periodically-driven, long-range interacting systems, with power-law exponent $alpha > d$, where $d$ is the dimensionality of the system. In this context, we predic
t the existence of a disorder-free, prethermal discrete time crystal in one dimension -- a phase strictly forbidden in the absence of long-range interactions. Finally, using a combination of analytic and numerical methods, we highlight key experimentally observable differences between such a prethermal time crystal and its many-body localized counterpart.
