15
$\begingroup$

I am reading the paper "Quantum Hidden Subgroup Algorithms: An Algorithmic Toolkit" by Samuel Lomonaco and Louis Kauffman from the book, "Mathematics of Quantum Computation and Quantum Technology." See also, this arxiv link.

The authors suggest that all quantum algorithms may be hidden subgroup algorithms in the sense that they all find hidden symmetries, i.e., hidden subgroups. Indeed, quantum hidden subgroup (QHS) algorithms encompass Deutsch-Jozsa, Simon's, Shor's factoring algorithm, and more.

The authors suggest of the following meta-procedure for quantum algorithm development:

  1. Meta-Step 1: Explicitly state the problem to be solved.

  2. Meta-Step 2: Rephrase the problem as a hidden symmetry.

  3. Meta-Step 3: Create a quantum algorithm to find the hidden symmetry.

The authors leaves the reader with the questions: "Can this meta-procedure be made more explicit?"

This is article is from 2008. Have their been any developments in the past 15 years building on this idea, or proving that all quantum algorithms are indeed hidden subgroup algorithms?

Improve this question
$\endgroup$
8
  • $\begingroup$ Perhaps if you can find a BQP-complete problem, it might be so… Can HHL be rephrased as a hidden subgroup problem? HHL is from 2010, and is BQP-complete, unlike the others you mention. $\endgroup$
    – Mark Spinelli
    Aug 17, 2022 at 22:11
  • $\begingroup$ HHL: given $A$ and $b$, find $x$ such that $Ax=b$. As a hidden subgroup: find the kernel (a subgroup of vectors) of the matrix $[A | -b]$. $\endgroup$
    – Sam Jaques
    Aug 18, 2022 at 7:03
  • 1
    $\begingroup$ @SamJaques very interesting - can you expand on that? What does the notation $[A\vert -b]$ mean? Is that a group itself? And under what operation- matrix multiplication? What is hidden? I have some ideas about your statement, but not positive. The kernel maps to $\mathbb 1$? Most quantum algorithms return an NP certificate - as generators of the hidden subgroup. But HHL doesn’t have a certificate that’s classically verifiable. If HHL could be reframed as a BQP-complete HSP, would that answer in the affirmative Lomomaco and Kauffman? $\endgroup$
    – Mark Spinelli
    Aug 18, 2022 at 11:22
  • $\begingroup$ I mean concatenation of matrices (not sure if there is a standard notation for that, sorry), so if $A$ is $n\times n$ then $[A|-b]$ is an $n\times(n+1)$ matrix where $-b$ is the last column. The group would be $\mathbb{C}^{n+1}$ under addition, where the kernel is the one-dimensional subspace spanned by $(x, 1)$. I guess HHL doesn't really solve this hidden subgroup problem, since it gives you $\vert x\rangle$, not $x$ itself. $\endgroup$
    – Sam Jaques
    Aug 18, 2022 at 11:43
  • 3
    $\begingroup$ Did We Overgeneralize to the Hidden Subgroup Problem? a blog post by @‪Dave Bacon $\endgroup$
    – Egretta.Thula
    Aug 23, 2022 at 5:53

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.