Exact quantum query complexity of computing Hamming weight modulo powers
of two and three
- URL: http://arxiv.org/abs/2112.14682v1
- Date: Wed, 29 Dec 2021 17:57:41 GMT
- Title: Exact quantum query complexity of computing Hamming weight modulo powers
of two and three
- Authors: Arjan Cornelissen and Nikhil S. Mande and Maris Ozols and Ronald de
Wolf
- Abstract summary: We show that the exact quantum query complexity of this problem is $leftlceil n (1 - 1/m) rightil$.
The upper bound is via an iterative query algorithm whose core components are the well-known 1-query quantum algorithm.
- Score: 2.1349209400003932
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of computing the Hamming weight of an $n$-bit string
modulo $m$, for any positive integer $m \leq n$ whose only prime factors are 2
and 3. We show that the exact quantum query complexity of this problem is
$\left\lceil n(1 - 1/m) \right\rceil$. The upper bound is via an iterative
query algorithm whose core components are the well-known 1-query quantum
algorithm (essentially due to Deutsch) to compute the Hamming weight a 2-bit
string mod 2 (i.e., the parity of the input bits), and a new 2-query quantum
algorithm to compute the Hamming weight of a 3-bit string mod 3.
We show a matching lower bound (in fact for arbitrary moduli $m$) via a
variant of the polynomial method [de Wolf, SIAM J. Comput., 32(3), 2003]. This
bound is for the weaker task of deciding whether or not a given $n$-bit input
has Hamming weight 0 modulo $m$, and it holds even in the stronger
non-deterministic quantum query model where an algorithm must have positive
acceptance probability iff its input evaluates to 1. For $m>2$ our lower bound
exceeds $n/2$, beating the best lower bound provable using the general
polynomial method [Theorem 4.3, Beals et al., J. ACM 48(4), 2001].
Related papers
- Logarithmic-Depth Quantum Circuits for Hamming Weight Projections [3.481985817302898]
We propose several quantum algorithms that realize a coherent Hamming weight projective measurement on an input pure state.
We analyze a depth-width trade-off for the corresponding quantum circuits, allowing for a depth reduction of the circuits at the cost of more control qubits.
arXiv Detail & Related papers (2024-04-10T16:35:36Z) - A simple lower bound for the complexity of estimating partition functions on a quantum computer [0.20718016474717196]
We study the complexity of estimating the partition function $mathsfZ(beta)=sum_xinchi e-beta H(x)$ for a Gibbs distribution characterized by the Hamiltonian $H(x)$.
We provide a simple and natural lower bound for quantum algorithms that solve this task by relying on reflections through the coherent encoding of Gibbs states.
arXiv Detail & Related papers (2024-04-03T02:38:49Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - On the exact quantum query complexity of $\text{MOD}_m^n$ and
$\text{EXACT}_{k,l}^n$ [0.0]
We present an exact quantum algorithm for computing $textMOD_mn$.
We show exact quantum query complexity of a broad class of symmetric functions that map $0,1n$ to a finite set $X$ is less than $n$.
arXiv Detail & Related papers (2023-03-20T08:17:32Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$.
We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM)
Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
arXiv Detail & Related papers (2022-06-07T18:00:01Z) - Pauli String Partitioning Algorithm with the Ising Model for
Simultaneous Measurement [0.0]
We propose an efficient algorithm for partitioning Pauli strings into subgroups, which can be simultaneously measured in a single quantum circuit.
Our partitioning algorithm drastically reduces the total number of measurements in a variational quantum eigensolver for a quantum chemistry.
arXiv Detail & Related papers (2022-05-09T01:49:21Z) - Exponential Separation between Quantum and Classical Ordered Binary
Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
We study quantum Ordered Binary Decision Diagrams($OBDD$) model.
We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables.
We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
arXiv Detail & Related papers (2022-04-22T12:37:56Z) - A quantum algorithm for computing the Carmichael function [0.0]
Quantum computers can solve many number theory problems efficiently.
This paper presents an algorithm that computes the Carmichael function for any integer $N$ with a probability as close to 1 as desired.
arXiv Detail & Related papers (2021-11-03T19:30:27Z) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05: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.