Analytical lower bound on query complexity for transformations of unknown unitary operations

• URL: http://arxiv.org/abs/2405.07625v2
• Date: Thu, 28 Nov 2024 05:07:31 GMT
• Title: Analytical lower bound on query complexity for transformations of unknown unitary operations
• Authors: Tatsuki Odake, Satoshi Yoshida, Mio Murao,
• Abstract summary: We establish analytical lower bounds for the query complexity of unitary inversion.<n>We extend our framework to the probabilistic setting, where transformations must succeed with a certain probability.
• Score: 0.8192907805418581
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent developments have revealed deterministic and exact protocols for performing complex conjugation, inversion, and transposition of a general $d$-dimensional unknown unitary operation using a finite number of queries to a black-box unitary operation. In this work, we establish analytical lower bounds for the query complexity of unitary inversion, transposition, and complex conjugation. Specifically, our lower bound of $d^2$ for unitary inversion demonstrates the asymptotic optimality of the deterministic exact inversion protocol, which operates with $O(d^2)$ queries. We introduce a novel framework utilizing differentiation to derive these lower bounds on query complexity for general differentiable functions $f: \mathrm{SU}(d)\to \mathrm{SU}(d)$. As a corollary, we prove that a catalytic protocol -- a new concept recently noted in the study of exact unitary inversion -- is impossible for unitary complex conjugation. Furthermore, we extend our framework to the probabilistic setting, where transformations must succeed with a certain probability, revealing a potential trade-off between the number of queries and the required success probability.

Related papers

• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
  We study the sample complexity of online reinforcement learning for nonlinear dynamical systems with continuous state and action spaces. Our algorithms are likely to be useful in practice, due to their simplicity, the ability to incorporate prior knowledge, and their benign transient behavior.
  arXiv  Detail & Related papers  (2025-01-27T10:01:28Z)
• Generalized Rényi entropy accumulation theorem and generalized quantum probability estimation [0.0]
  entropy accumulation theorem is a powerful tool in the security analysis of many device-dependent and device-independent cryptography protocols. It relies on the construction of an affine min-tradeoff function, which can often be challenging to construct optimally in practice. We deriving a new entropy accumulation bound, which yields significantly better finite-size performance.
  arXiv  Detail & Related papers  (2024-05-09T17:11:00Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• Complexity-Theoretic Implications of Multicalibration [8.315801422499863]
  Multiaccurate predictors satisfy a stronger condition: they are calibrated on each set in the collection. This complexity-theoretic Regularity Lemma is known to have implications in different areas. We show that every function (regardless of its hardness) has a small collection of disjoint hardcore sets.
  arXiv  Detail & Related papers  (2023-12-28T18:53:21Z)
• The Complexity of Being Entangled [0.0]
  Nielsen's approach to quantum state complexity relates the minimal number of quantum gates required to prepare a state to the length of geodesics computed with a certain norm on the manifold of unitary transformations. For a bipartite system, we investigate binding complexity, which corresponds to norms in which gates acting on a single subsystem are free of cost.
  arXiv  Detail & Related papers  (2023-11-07T19:00:02Z)
• Explicit error bounds for entanglement transformations between sparse multipartite states [0.0]
  A nontrivial family of such functional exponents has recently been constructed. We derive a new regularised formula for these functionals in terms of a subadditive upper bound. Our results provide explicit bounds on the success probability of transformations by local operations and classical communication.
  arXiv  Detail & Related papers  (2023-09-20T16:06:48Z)
• Reconstructing $S$-matrix Phases with Machine Learning [49.1574468325115]
  We apply modern machine learning techniques to studying the unitarity constraint. We find a new phase-ambiguous solution which pushes the known limit on such solutions significantly beyond the previous bound.
  arXiv  Detail & Related papers  (2023-08-18T10:29:26Z)
• Generalization Guarantees via Algorithm-dependent Rademacher Complexity [33.408679482592426]
  We propose a measure to control generalization error, which is the empirical Rademacher complexity of an algorithm- and data-dependent hypothesis class. We obtain novel bounds based on the finite fractal dimension, which (a) extend previous fractal-type bounds from continuous to finite hypothesis classes, and (b) avoid a mutual information term.
  arXiv  Detail & Related papers  (2023-07-04T18:37:38Z)
• Unitary property testing lower bounds by polynomials [0.15229257192293197]
  We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary. Characterizing the complexity of these problems requires new algorithmic techniques and lower bound methods. We present a unitary property testing-based approach towards an oracle separation between $mathsfQMA$ and $mathsfQMA(2)$.
  arXiv  Detail & Related papers  (2022-10-12T03:01:00Z)
• Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly [0.9208007322096532]
  We consider the most general class of protocols transforming unknown unitary operations within the quantum circuit model. In the proposed protocol, the input qubit-unitary operation is called 4 times to achieve the inverse operation. We show a method to reduce the large search space representing all possible protocols.
  arXiv  Detail & Related papers  (2022-09-07T03:33:09Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  We propose a family of Riemannian algorithms generalizing and extending the seminal approximation framework of Robbins and Monro. Compared to their Euclidean counterparts, Riemannian algorithms are much less understood due to lack of a global linear structure on the manifold. We provide a general template of almost sure convergence results that mirrors and extends the existing theory for Euclidean Robbins-Monro schemes.
  arXiv  Detail & Related papers  (2022-06-14T12:30:11Z)
• $O(N^2)$ Universal Antisymmetry in Fermionic Neural Networks [107.86545461433616]
  We propose permutation-equivariant architectures, on which a determinant Slater is applied to induce antisymmetry. FermiNet is proved to have universal approximation capability with a single determinant, namely, it suffices to represent any antisymmetric function. We substitute the Slater with a pairwise antisymmetry construction, which is easy to implement and can reduce the computational cost to $O(N2)$.
  arXiv  Detail & Related papers  (2022-05-26T07:44:54Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Bounds on quantum evolution complexity via lattice cryptography [0.0]
  We address the difference between integrable and chaotic motion in quantum theory as manifested by the complexity of the corresponding evolution operators. Complexity is understood here as the shortest geodesic distance between the time-dependent evolution operator and the origin within the group of unitaries.
  arXiv  Detail & Related papers  (2022-02-28T16:20:10Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  We analyze the problem of estimating optimal $Q$-value functions for a discounted Markov decision process with discrete states and actions. Using a local minimax framework, we show that this functional arises in lower bounds on the accuracy on any estimation procedure. In the other direction, we establish the sharpness of our lower bounds, up to factors logarithmic in the state and action spaces, by analyzing a variance-reduced version of $Q$-learning.
  arXiv  Detail & Related papers  (2021-06-28T00:38:54Z)
• Quantifying and Improving Transferability in Domain Generalization [53.16289325326505]
  Out-of-distribution generalization is one of the key challenges when transferring a model from the lab to the real world. We formally define transferability that one can quantify and compute in domain generalization. We propose a new algorithm for learning transferable features and test it over various benchmark datasets.
  arXiv  Detail & Related papers  (2021-06-07T14:04:32Z)
• Nonparametric approximation of conditional expectation operators [0.3655021726150368]
  We investigate the approximation of the $L2$-operator defined by $[Pf](x) := mathbbE[ f(Y) mid X = x ]$ under minimal assumptions. We prove that $P$ can be arbitrarily well approximated in operator norm by Hilbert-Schmidt operators acting on a reproducing kernel space.
  arXiv  Detail & Related papers  (2020-12-23T19:06:12Z)
• Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
  We introduce a new scalable approximation for Gaussian processes with provable guarantees which hold simultaneously over its entire parameter space. Our approximation is obtained from an improved sample complexity analysis for sparse spectrum Gaussian processes (SSGPs)
  arXiv  Detail & Related papers  (2020-11-17T05:41:50Z)
• Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step [2.0196229393131726]
  We analyze inexact and versions of the CGALP algorithm developed in the authors' previous paper. This allows one to compute some gradients, terms, and/or linear minimization oracles in an inexact fashion. We show convergence of the Lagrangian to an optimum and feasibility of the affine constraint.
  arXiv  Detail & Related papers  (2020-05-11T14:52:16Z)
• Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning [63.64636047748605]
  We develop a new theoretical framework to provide convergence guarantee for the general multi-step MAML algorithm. In particular, our results suggest that an inner-stage step needs to be chosen inversely proportional to $N$ of inner-stage steps in order for $N$ MAML to have guaranteed convergence.
  arXiv  Detail & Related papers  (2020-02-18T19:17:54Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.