Decoded Quantum Interferometry, a new approach to quantum optimisation, presents a significant challenge to classical computation, according to research led by Kunal Marwaha and Bill Fefferman from the University of Chicago, alongside Alexandru Gheorghiu and Vojtech Havlicek from IBM Quantum. The team demonstrates that the difficulty of simulating this process stems from the need to identify an enormous, hidden subset within the calculation, a task that lacks the simplifying structure found in other complex problems. Their work rules out arguments linking this quantum method to achieving quantum supremacy, instead revealing a connection to established principles of coding theory and the preparation of quantum states resembling an obscured harmonic oscillator. This discovery highlights the unique computational power of a specific mathematical operation, a discrete Hermite transform, which currently lacks an efficient classical equivalent.
Hidden subset problems often lack obvious group structure. Instead, the team shows that DQI implements a bound derived from existential coding theory, based on the MacWilliams identity, and prepares a quantum state within an obfuscated quantum harmonic oscillator. Both perspectives require a coherent application of a discrete Hermite transform, a process lacking a natural classical analogue. Researchers established that simulating DQI classically is challenging because it requires identifying an exponentially large hidden subset. To rule out arguments based on quantum supremacy, the team proved DQI can be simulated within a specific level of the polynomial hierarchy. This work reveals DQI implements a bound derived from existential coding theory, specifically the MacWilliams identity, reinterpreted as a discretized Fourier transform.
This allows the team to show DQI prepares a quantum state within an obfuscated quantum harmonic oscillator. Crucially, this requires a coherent application of a discrete Hermite transform, lacking a direct classical analogue. The researchers leveraged established results from coding theory, including the use of Kravchuk polynomials and bounds on covering radius, to construct a good distribution of codewords, naturally leading to a quantum algorithm for state preparation. To implement this on a digital quantum computer, the team developed a method for discretizing the quantum harmonic oscillator while preserving its eigenspectrum, representing the oscillator’s eigenstates as Fourier transforms of n-qubit Dicke states. Furthermore, they explored obfuscating these eigenstates with a function derived from the linear code, embedding these obfuscated states within a low-energy subspace of the quantum harmonic oscillator. This simulation, achieved using an NP oracle, allows for approximate sampling from a distribution closely mirroring the output of the DQI circuit with a multiplicative error. Further research reveals a connection between DQI and foundational principles of coding theory, specifically linear programming techniques used to compare the rate and distance of linear codes. Scientists discovered that the existence of approximate solutions matching DQI’s performance was previously known as early as 1990, utilizing Fourier-analytic identities to design a good distribution of codewords.
Crucially, the team demonstrated that this previously known bound can be made constructive using a quantum algorithm, coherently implementing a Fourier transform, suggesting a quantum advantage in preparing this distribution. Experiments show that DQI prepares a state within a quantum harmonic oscillator, where energy corresponds to the number of correctable errors and position represents the satisfying fraction of an assignment. Measurements confirm that the optimal state is concentrated on a position matching the semicircle law, with exponentially many codewords located at this point, suggesting that preparing these states is possible with a quantum device but remains challenging for classical computation. These findings improve understanding of DQI’s power and suggest avenues for designing new algorithms with potential quantum advantage. Theorems demonstrate that procedures for sampling from a distribution close to the DQI output run in randomized polynomial time with access to an NP oracle. While DQI can be simulated at a certain level of computational complexity, the team established that preparing the quantum states necessary for sampling solutions is uniquely achievable with a quantum computer. Specifically, the process relies on coherently error-correcting in the Fourier basis, a technique for which a classical equivalent remains elusive. The findings reveal that DQI effectively encodes potential solutions to optimization problems within the states of a harmonic oscillator, preparing a state concentrated on codewords at a specific distance from a known vector.
Importantly, the researchers proved the existence of an exponentially large number of these codewords, demonstrating that DQI identifies approximate solutions among a vast, yet identifiable, set. This concentration of solutions occurs within a “semicircle law” region, allowing the identification of codewords at various distances from the target vector, a feat not currently achievable through classical methods. The authors acknowledge that their analysis primarily focuses on binary codes and a specific target vector, though they suggest the results likely extend to more general scenarios. Future work could explore the applicability of these findings to different types of optimization problems and finite fields. While the team has demonstrated the existence of numerous solutions within a defined region, efficiently finding these solutions classically remains an open challenge, highlighting a key area for continued investigation.