skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: The role of randomness in quantum state certification with unentangled measurements
We study quantum state certification using unentangled quantum measurements, namely measurements which operate only on one copy of the state at a time. When there is a common source of randomness available and the unentangled measurements are chosen based on this randomness, prior work has shown that copies are necessary and sufficient. We show a separation between algorithms with and without randomness. We develop a lower bound framework for both fixed and randomized measurements that relates the hardness of testing to the well-established Lüders rule. More precisely, we obtain lower bounds for randomized and fixed schemes as a function of the eigenvalues of the Lüders channel which characterizes one possible post-measurement state transformation.  more » « less
Award ID(s):
1846300
PAR ID:
10541062
Author(s) / Creator(s):
;
Editor(s):
Agrawal, Shipra; Roth, Aaron
Publisher / Repository:
Proceedings of Machine Learning Research
Date Published:
Format(s):
Medium: X
Location:
Edmonton, Canada
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP), Track A)
    We investigate the power of randomness in two-party communication complexity. In particular, we study the model where the parties can make a constant number of queries to a function with an efficient one-sided-error randomized protocol. The complexity classes defined by this model comprise the Randomized Boolean Hierarchy, which is analogous to the Boolean Hierarchy but defined with one-sided-error randomness instead of nondeterminism. Our techniques connect the Nondeterministic and Randomized Boolean Hierarchies, and we provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove that the Randomized Boolean Hierarchy does not collapse, and we prove a query-to-communication lifting theorem for all levels of the Nondeterministic Boolean Hierarchy and use it to resolve an open problem stated in the paper by Halstenberg and Reischuk (CCC 1988) which initiated the study of this hierarchy. 
    more » « less
  2. ; ; (, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences)
    The mixedness of one share of a pure bipartite state determines whether the overall state is a separable, unentangled one. Here we consider quantum computational tests of mixedness, and we derive an exact expression of the acceptance probability of such tests as the number of copies of the state becomes larger. We prove that the analytical form of this expression is given by the cycle index polynomial of the symmetric group S k , which is itself related to the Bell polynomials. After doing so, we derive a family of quantum separability tests, each of which is generated by a finite group; for all such algorithms, we show that the acceptance probability is determined by the cycle index polynomial of the group. Finally, we produce and analyse explicit circuit constructions for these tests, showing that the tests corresponding to the symmetric and cyclic groups can be executed with O ( k 2 ) and O ( k log ⁡ ( k ) ) controlled-SWAP gates, respectively, where k is the number of copies of the state being tested. 
    more » « less
  3. ; ; (, Quantum)
    Classical shadows (CS) offer a resource-efficient means to estimate quantum observables, circumventing the need for exhaustive state tomography. Here, we clarify and explore the connection between CS techniques and least squares (LS) and regularized least squares (RLS) methods commonly used in machine learning and data analysis. By formal identification of LS and RLS ``shadows'' completely analogous to those in CS---namely, point estimators calculated from the empirical frequencies of single measurements---we show that both RLS and CS can be viewed as regularizers for the underdetermined regime, replacing the pseudoinverse with invertible alternatives. Through numerical simulations, we evaluate RLS and CS from three distinct angles: the tradeoff in bias and variance, mismatch between the expected and actual measurement distributions, and the interplay between the number of measurements and number of shots per measurement.Compared to CS, RLS attains lower variance at the expense of bias, is robust to distribution mismatch, and is more sensitive to the number of shots for a fixed number of state copies---differences that can be understood from the distinct approaches taken to regularization. Conceptually, our integration of LS, RLS, and CS under a unifying ``shadow'' umbrella aids in advancing the overall picture of CS techniques, while practically our results highlight the tradeoffs intrinsic to these measurement approaches, illuminating the circumstances under which either RLS or CS would be preferred, such as unverified randomness for the former or unbiased estimation for the latter. 
    more » « less
  4. ; (, International Mathematics Research Notices)
    The randomized quantum marginal problem asks about the joint distribution of the partial traces (“marginals”) of a uniform random Hermitian operator with fixed spectrum acting on a space of tensors. We introduce a new approach to this problem based on studying the mixed moments of the entries of the marginals. For randomized quantum marginal problems that describe systems of distinguishable particles, bosons, or fermions, we prove formulae for these mixed moments, which determine the joint distribution of the marginals completely. Our main tool is Weingarten calculus, which provides a method for computing integrals of polynomial functions with respect to Haar measure on the unitary group. As an application, in the case of two distinguishable particles, we prove some results on the asymptotic behavior of the marginals as the dimension of one or both Hilbert spaces goes to infinity. 
    more » « less
  5. ; (, Erkenntnis)
    Abstract The present paper shows how one might model Everettian quantum mechanics using hyperfinitely many worlds. A hyperfinite model allows one to consider idealized measurements of observables with continuous-valued spectra where different outcomes are associated with possibly infinitesimal probabilities. One can also prove hyperfinite formulations of Everett’s limiting relative-frequency and randomness properties, theorems he considered central to his formulation of quantum mechanics. Finally, this model provides an intuitive framework in which to consider no-collapse formulations of quantum mechanics more generally. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email