A new quantum algorithm for the hidden shift problem in $\mathbb{Z}_{2^t}^n$

• URL: http://arxiv.org/abs/2102.04171v1
• Date: Mon, 8 Feb 2021 13:01:33 GMT
• Title: A new quantum algorithm for the hidden shift problem in $\mathbb{Z}_{2^t}^n$
• Authors: Gergely Cs\'aji
• Abstract summary: We give a solution to the case when $k$ is a power of 2, which has running time in $nlog (k) It can be a useful tool in the general case of the hidden shift and hidden problems too.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In this paper we make a step towards a time and space efficient algorithm for the hidden shift problem for groups of the form $\mathbb{Z}_k^n$. We give a solution to the case when $k$ is a power of 2, which has polynomial running time in $n$, and only uses quadratic classical, and linear quantum space in $n\log (k)$. It can be a useful tool in the general case of the hidden shift and hidden subgroup problems too, since one of the main algorithms made to solve them can use this algorithm as a subroutine in its recursive steps, making it more efficient in some instances.

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)
• Fast quantum integer multiplication with zero ancillas [0.5755004576310334]
  We introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits. The only qubits involved are the input and output registers themselves. Our algorithm has the potential to outperform previous problem sizes relevant in practice.
  arXiv  Detail & Related papers  (2024-03-26T18:00:03Z)
• A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
  We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al. A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$. We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
  arXiv  Detail & Related papers  (2024-02-09T19:01:48Z)
• Do you know what q-means? [50.045011844765185]
  Clustering is one of the most important tools for analysis of large datasets. We present an improved version of the "$q$-means" algorithm for clustering. We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• An Efficient Quantum Factoring Algorithm [0.27195102129094995]
  We show that $n$bit integers can be factorized by independently running a quantum circuit with $tildeO(n3/2)$. The correctness of the algorithm relies on a number-theoretic assumption reminiscent of those used in subexponential classical factorization algorithms.
  arXiv  Detail & Related papers  (2023-08-12T13:57:38Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  We introduce efficient $(1+varepsilon)$-approximation algorithms for the binary matrix factorization (BMF) problem. The goal is to approximate $mathbfA$ as a product of low-rank factors. Our techniques generalize to other common variants of the BMF problem.
  arXiv  Detail & Related papers  (2023-06-02T18:55:27Z)
• Quantum Speedups for Bayesian Network Structure Learning [0.0]
  For networks with $n$ nodes, the fastest known algorithms run in time $O(cn)$ in the worst case, with no improvement in two decades. Inspired by recent advances in quantum computing, we ask whether BNSL admits a quantum speedup. We give two algorithms achieving $c leq 1.817$ and $c leq 1.982$.
  arXiv  Detail & Related papers  (2023-05-31T09:15:28Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• A Quantum Polynomial-Time Solution to The Dihedral Hidden Subgroup Problem [1.189332466445755]
  We present a-time quantum algorithm for the Hidden Subgroup Problem over $mathbbD_2n$. By focusing on structure encoded in the codomain of the problem, we develop an algorithm which uses this structure to direct a "walk" down the subgroup lattice of $mathbbD_2n$ terminating at the hidden subgroup.
  arXiv  Detail & Related papers  (2022-02-19T23:51:15Z)
• A polynomial time and space heuristic algorithm for T-count [2.28438857884398]
  This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes. We consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford+T gate set, a universal gate set.
  arXiv  Detail & Related papers  (2020-06-22T17:21:41Z)

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.