Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2205.06977 · Communications in Mathematical Physics

Hay from the Haystack: Explicit Examples of Exponential Quantum Circuit Complexity

Yifan Jia, Michael M. Wolf

Published May 7, 2023• 11 citations
arXivHTMLPDF
DOI
10.1007/s00220-023-04720-x

Related papers

Finding a Needle in a Haystack: From Baldwin Effect to Quantum Computation

Akira Imada

If we want to break someone else's PIN (personal identification number) of, say, an ATM (automated teller machine), how many trials would be necessary when we want to be efficient? This is a sort of what we calla-needle-in-a-hay-stackproblem. In 1987, in their wonderful paper, Hinton & Nowlan proposed a genetic algorithm with a needle being a unique configuration of 20-bit binary string while all other configurations being a haystack. What they proposed was to exploit alifetimelearningof individuals in their genetic algorithm, calling it the Baldwin effectinacomputer. Since then there has been a fair amount of exploration of this effect, claiming, "this is a-needle-in-a-hay-stack problem, and we've found a more efficient algorithm than a random search." Some of them, however, were found to be the results of an effect oflike-to-hear-what-we-would-like-to-hear. In this talk, we will try a bird's eye view on a few examples we have had so far, and how they were explored, including the approach by means of quantum computation which claims, "The steps to find a needle areO(radicN) while those of exhaustive search by a traditional computer are O(N) whereNis the number of search points."

International Conference on Computer Information Systems and Industrial Management Applications (CISIM)•Jun 1, 2007•3 citations

Complexity Lower Bounds for Quantum Circuits

Mika Hirvensalo

Springer eBooks•Jan 1, 2001•0 citations

Complexity Lower Bounds for Quantum Circuits

Mika Hirvensalo

Springer eBooks•Jan 1, 2004•0 citations

Explicit non-free tensors

Maxim van den Berg, Matthias Christandl, Vladimir Lysikov +3 more

Free tensors are tensors which, after a change of bases, have free support: any two distinct elements of its support differ in at least two coordinates. They play a distinguished role in the theory of bilinear complexity, in particular in Strassen's duality theory for asymptotic rank. Within the context of quantum information theory, where tensors are interpreted as multiparticle quantum states, freeness corresponds to a type of multiparticle Schmidt decomposition. In particular, if a state is free in a given basis, the reduced density matrices are diagonal. Although generic tensors in $\mathbb{C}^n \otimes \mathbb{C}^n \otimes \mathbb{C}^n$ are non-free for $n \geq 4$ by parameter counting, no explicit non-free tensors were known until now. We solve this hay in a haystack problem by constructing explicit tensors that are non-free for every $n \geq 3$. In particular, this establishes that non-free tensors exist in $\mathbb{C}^n \otimes \mathbb{C}^n \otimes \mathbb{C}^n$, where they are not generic. To establish non-freeness, we use results from geometric invariant theory and the theory of moment polytopes. In particular, we show that if a tensor $T$ is free, then there is a tensor $S$ in the GL-orbit closure of $T$, whose support is free and whose moment map image is the minimum-norm point of the moment polytope of $T$. This implies a reduction for checking non-freeness from arbitrary basis changes of $T$ to unitary basis changes of $S$. The unitary equivariance of the moment map can then be combined with the fact that tensors with free support have diagonal moment map image, in order to further restrict the set of relevant basis changes.

arXiv:2503.22650•Mar 28, 2025•2 citations

Computational complexity and applications of quantum algorithm

Satoshi Iriyama, Makoto Ohya

Applied Mathematics and Computation•Jun 24, 2011•2 citations

A QAOA-inspired circuit for Grover's unstructured search using a transverse field

Jiang Zhang, Eleanor Gilbert Rieffel, Zhihui Wang

Inspired by a class of algorithms proposed by Farhi et al., namely the quantum approximate optimization algorithm (QAOA), we present a circuit-based quantum algorithm to search for a needle in a haystack, obtaining the same quadratic speedup achieved by Grover's original algorithm. In our algorithm, the problem Hamiltonian (oracle) and a transverse field are applied alternately to the system in a periodic manner. We introduced a novel technique, a spin-coherent-state approach, to analyze the composite unitary in a single period. This composite unitary drives a closed transition between two states that have high degrees of overlap with the initial state and the target state, respectively. The transition rate in our algorithm is of order $\Theta(1/\sqrt N)$, and the overlaps are of order $\Theta(1)$, yielding a nearly optimal query complexity of $T\simeq \sqrt N (\pi/2\sqrt 2\,)$. Our algorithm is the first example of a QAOA circuit that demonstrates a quantum advantage with large number of iterations that is not derived from Trotterization of an adiabatic quantum optimization (AQO) algorithm. It also suggests that the analysis required to understand QAOA circuits involves a very different process from estimating the energy gap of a Hamiltonian in AQO.

•Feb 8, 2017•4 citations
If we want to break someone else's PIN (personal identification number) of, say, an ATM (automated teller machine), how many trials would be necessary when we want to be efficient? This is a sort of what we calla-needle-in-a-hay-stackproblem. In 1987, in their wonderful paper, Hinton & Nowlan proposed a genetic algorithm with a needle being a unique configuration of 20-bit binary string while all other configurations being a haystack. What they proposed was to exploit alifetimelearningof individuals in their genetic algorithm, calling it the Baldwin effectinacomputer. Since then there has been a fair amount of exploration of this effect, claiming, "this is a-needle-in-a-hay-stack problem, and we've found a more efficient algorithm than a random search." Some of them, however, were found to be the results of an effect oflike-to-hear-what-we-would-like-to-hear. In this talk, we will try a bird's eye view on a few examples we have had so far, and how they were explored, including the approach by means of quantum computation which claims, "The steps to find a needle areO(radicN) while those of exhaustive search by a traditional computer are O(N) whereNis the number of search points."
Free tensors are tensors which, after a change of bases, have free support: any two distinct elements of its support differ in at least two coordinates. They play a distinguished role in the theory of bilinear complexity, in particular in Strassen's duality theory for asymptotic rank. Within the context of quantum information theory, where tensors are interpreted as multiparticle quantum states, freeness corresponds to a type of multiparticle Schmidt decomposition. In particular, if a state is free in a given basis, the reduced density matrices are diagonal. Although generic tensors in Cn⊗Cn⊗Cn\mathbb{C}^n \otimes \mathbb{C}^n \otimes \mathbb{C}^nCn⊗Cn⊗Cn are non-free for n≥4n \geq 4n≥4 by parameter counting, no explicit non-free tensors were known until now. We solve this hay in a haystack problem by constructing explicit tensors that are non-free for every n≥3n \geq 3n≥3. In particular, this establishes that non-free tensors exist in Cn⊗Cn⊗Cn\mathbb{C}^n \otimes \mathbb{C}^n \otimes \mathbb{C}^nCn⊗Cn⊗Cn, where they are not generic. To establish non-freeness, we use results from geometric invariant theory and the theory of moment polytopes. In particular, we show that if a tensor TTT is free, then there is a tensor SSS in the GL-orbit closure of TTT, whose support is free and whose moment map image is the minimum-norm point of the moment polytope of TTT. This implies a reduction for checking non-freeness from arbitrary basis changes of TTT to unitary basis changes of SSS. The unitary equivariance of the moment map can then be combined with the fact that tensors with free support have diagonal moment map image, in order to further restrict the set of relevant basis changes.
Inspired by a class of algorithms proposed by Farhi et al., namely the quantum approximate optimization algorithm (QAOA), we present a circuit-based quantum algorithm to search for a needle in a haystack, obtaining the same quadratic speedup achieved by Grover's original algorithm. In our algorithm, the problem Hamiltonian (oracle) and a transverse field are applied alternately to the system in a periodic manner. We introduced a novel technique, a spin-coherent-state approach, to analyze the composite unitary in a single period. This composite unitary drives a closed transition between two states that have high degrees of overlap with the initial state and the target state, respectively. The transition rate in our algorithm is of order Θ(1/N)\Theta(1/\sqrt N)Θ(1/N​), and the overlaps are of order Θ(1)\Theta(1)Θ(1), yielding a nearly optimal query complexity of T≃N(π/22 )T\simeq \sqrt N (\pi/2\sqrt 2\,)T≃N​(π/22​). Our algorithm is the first example of a QAOA circuit that demonstrates a quantum advantage with large number of iterations that is not derived from Trotterization of an adiabatic quantum optimization (AQO) algorithm. It also suggests that the analysis required to understand QAOA circuits involves a very different process from estimating the energy gap of a Hamiltonian in AQO.