Concise and Efficient Quantum Algorithms for Distribution Closeness Testing

• URL: http://arxiv.org/abs/2302.06084v1
• Date: Mon, 13 Feb 2023 04:03:59 GMT
• Title: Concise and Efficient Quantum Algorithms for Distribution Closeness Testing
• Authors: Lvzhou Li and Jingquan Luo
• Abstract summary: We study the impact of quantum computation on the fundamental problem of testing the property of distributions. We propose the currently best quantum algorithms for this problem under the metrics of $l1$-distance and $l2$-distance.
• Score: 0.2741266294612775
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the impact of quantum computation on the fundamental problem of testing the property of distributions. In particular, we focus on testing whether two unknown classical distributions are close or far enough, and propose the currently best quantum algorithms for this problem under the metrics of $l^1$-distance and $l^2$-distance. Compared with the latest results given in \cite{gilyen2019distributional} which relied on the technique of quantum singular value transformation (QSVT), our algorithms not only have lower complexity, but also are more concise.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice [0.0]
  Variational quantum algorithms and, in particular, variants of the varational quantum eigensolver have been proposed to address optimization (CO) problems. We numerically investigate what this scaling result means in practice for solving CO problems using Max-Cut as a benchmark.
  arXiv  Detail & Related papers  (2024-08-06T09:57:34Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Variational Quantum Algorithms for the Allocation of Resources in a Cloud/Edge Architecture [1.072460284847973]
  We show that Variational Quantum Algorithms can be a viable alternative to classical algorithms in the near future. In particular, we compare the performances, in terms of success probability, of two algorithms, i.e., Quantum Approximate Optimization Algorithm (QAOA) and Variational Quantum Eigensolver (VQE) The simulation experiments, performed for a set of simple problems, %CM230124 that involve a Cloud and two Edge nodes, show that the VQE algorithm ensures better performances when it is equipped with appropriate circuit textitansatzes that are able to restrict the search space
  arXiv  Detail & Related papers  (2024-01-25T17:37:40Z)
• Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions [13.16814860487575]
  We present quantum algorithms for sampling from nonlogconcave probability distributions. $f$ can be written as a finite sum $f(x):= frac1Nsum_k=1N f_k(x)$.
  arXiv  Detail & Related papers  (2023-10-17T17:55:32Z)
• Making the cut: two methods for breaking down a quantum algorithm [0.0]
  It remains a major challenge to find quantum algorithms that may reach computational advantage in the present era of noisy, small-scale quantum hardware. We identify and characterize two methods of breaking down'' quantum algorithms into rounds of lower (query) depth. We show that for the first problem parallelization offers the best performance, while for the second is the better choice.
  arXiv  Detail & Related papers  (2023-05-17T18:00:06Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Distributed quantum algorithm for Simon's problem [2.26741603346646]
  We study the Simon's problem in distributed scenarios and design a distributed quantum algorithm to solve the problem. The novel computing architecture of distributed quantum computing is expected to reduce the noise and depth of quantum circuits.
  arXiv  Detail & Related papers  (2022-04-25T01:22:22Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)

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.