Related papers: On the Complexity of Decoded Quantum Interferometry

On the Complexity of Decoded Quantum Interferometry

URL: http://arxiv.org/abs/2509.14443v1
Date: Wed, 17 Sep 2025 21:31:58 GMT
Title: On the Complexity of Decoded Quantum Interferometry
Authors: Kunal Marwaha, Bill Fefferman, Alexandru Gheorghiu, Vojtech Havlicek,
Abstract summary: We study the complexity of Decoded Quantum Interferometry (DQI), a recently proposed quantum algorithm for approximate optimization.<n>We argue that DQI is hard to classically simulate, and that the hardness comes from locating an exponentially large hidden subset.
Score: 39.951444958798014
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study the complexity of Decoded Quantum Interferometry (DQI), a recently proposed quantum algorithm for approximate optimization. We argue that DQI is hard to classically simulate, and that the hardness comes from locating an exponentially large hidden subset. This type of hardness is shared by Shor's algorithm, but the hidden subset here has no apparent group structure. We first prove that DQI can be simulated in a low level of the polynomial hierarchy, ruling out hardness arguments related to quantum supremacy. Instead, we show that DQI implements an existential coding theory bound based on the MacWilliams identity, and that it prepares a state within an obfuscated quantum harmonic oscillator. Both viewpoints require a coherent application of a discrete Hermite transform, which has no natural classical analog.

Related papers

On the hardness of cloning and connections to representation theory [0.0]
We conjecture about cloning algorithms for maximally entangled states over hidden subspaces. The conjecture and result follow from connections between quantum computation and representation theory.
arXiv Detail & Related papers (2024-11-18T18:19:08Z)
Founding Quantum Cryptography on Quantum Advantage, or, Towards Cryptography from $\mathsf{\#P}$-Hardness [10.438299411521099]
Recent separations have raised the tantalizing possibility of building quantum cryptography from sources of hardness that persist even if hierarchy collapses. We show that quantum cryptography can be based on the extremely mild assumption that $mathsfP#P notsubseteq mathsf(io)BQP/qpoly$.
arXiv Detail & Related papers (2024-09-23T17:45:33Z)
Depth scaling of unstructured search via quantum approximate optimization [0.0]
Variational quantum algorithms have become the de facto model for current quantum computations. One such problem is unstructured search which consists on finding a particular bit of string. We trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity.
arXiv Detail & Related papers (2024-03-22T18:00:03Z)
Taming Quantum Time Complexity [45.867051459785976]
We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z)
Learning the Complexity of Weakly Noisy Quantum States [0.5662299435213419]
We present an efficient learning algorithm, that leverages the classical shadow representation of target quantum states, to predict the circuit complexity of weakly noisy quantum states.<n>Our result builds a bridge between the learning algorithm and quantum state complexity, highlighting the power of the learning algorithm in characterizing intrinsic properties of quantum states.
arXiv Detail & Related papers (2023-03-31T06:02:44Z)
stateQIP = statePSPACE [0.15229257192293197]
We study the relation between two such state classes:SDPPSPACE, and stateQIP. Our main result is the reverse inclusion, stateQIP $subseteq$ statePSPACE. We also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum space.
arXiv Detail & Related papers (2023-01-18T19:00:17Z)
Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z)
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)
A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography. In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
arXiv Detail & Related papers (2022-05-07T03:15:15Z)
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)
Depth-efficient proofs of quantumness [77.34726150561087]
A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover. In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
arXiv Detail & Related papers (2021-07-05T17:45:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.