techlist.io
KR EN

quantum-algorithms

2 posts

google

A new quantum toolkit for optimization (opens in new tab)

Researchers at Google Quantum AI have introduced Decoded Quantum Interferometry (DQI), a new quantum algorithm designed to tackle optimization problems that remain intractable for classical supercomputers. By leveraging the wavelike nature of quantum mechanics to create specific interference patterns, the algorithm converts complex optimization tasks into high-dimensional lattice decoding problems. This breakthrough provides a theoretical framework where large-scale, error-corrected quantum computers could eventually outperform classical methods by several orders of magnitude on commercially relevant tasks. ### Linking Optimization to Lattice Decoding * The DQI algorithm functions by mapping the cost landscape of an optimization problem onto a periodic lattice structure. * The "decoding" aspect involves identifying the nearest lattice element to a specific point in space, a task that becomes exponentially difficult for classical computers as dimensions increase into the hundreds or thousands. * By using quantum interference to bridge these fields, researchers can apply decades of sophisticated classical decoding research—originally developed for data storage and transmission—to solve optimization challenges. * This approach is unique because it requires a quantum computer to leverage these classical decoding algorithms in a way that conventional hardware cannot. ### Solving the Optimal Polynomial Intersection (OPI) Problem * The most significant application of DQI is for the OPI problem, where the goal is to find a low-degree polynomial that intersects the maximum number of given target points. * OPI is a foundational task in data science (polynomial regression), cryptography, and digital error correction, yet it remains "hopelessly difficult" for classical algorithms in many scenarios. * DQI transforms the OPI problem into a task of decoding Reed-Solomon codes, a family of codes widely used in technologies like QR codes and DVDs. * Technical analysis indicates a massive performance gap: certain OPI instances could be solved by a quantum computer in approximately a few million operations, while the most efficient classical algorithms would require over $10^{23}$ (one hundred sextillion) operations. ### Practical Conclusion As quantum hardware moves toward the era of error correction, Decoded Quantum Interferometry identifies a specific class of "NP-hard" problems where quantum machines can provide a clear win. Researchers and industries focusing on cryptography and complex data regression should monitor DQI as a primary candidate for demonstrating the first generation of commercially viable quantum advantage in optimization.

quantum-algorithmsquantum-computingoptimizationdecoded-quantum-interferometry+4
google

A verifiable quantum advantage (opens in new tab)

Google Quantum AI researchers have introduced "Quantum Echoes," a new algorithm designed to measure Out-of-Time-Order Correlators (OTOCs) to characterize quantum chaos. By demonstrating this task on the 103-qubit Willow chip, the team has achieved a verifiable quantum advantage that surpasses the limitations of previous random circuit sampling techniques. This work establishes a direct path toward solving practical problems in physics and chemistry, such as Hamiltonian learning, through the use of stable and reproducible quantum expectation values. ## Limitations of Random Circuit Sampling * While the 2019 "quantum supremacy" milestone proved quantum computers could outperform classical ones, the bitstring sampling method used was difficult to verify and lacked practical utility. * In large-scale quantum systems, specific bitstrings rarely repeat, which restricts the ability to extract useful, actionable information from the computation. * The Quantum Echoes approach shifts focus to quantum expectation values—such as magnetization, density, and velocity—which remain consistent across different quantum computers and are computationally verifiable. ## The Quantum Echoes Algorithm and OTOCs * The algorithm measures OTOCs, which represent the state of a single qubit after a series of "forward" ($U$) and "backward" ($U^\dagger$) evolutions. * In the experiment, 103 qubits on the Willow processor underwent evolution through random quantum circuits to reach a highly chaotic state. * A perturbation (gate $B$) is applied between the forward and backward evolutions; if the system is chaotic, this small change triggers a "butterfly effect," resulting in a final state significantly different from the initial one. * Higher-order OTOCs involve multiple "round trips" of these evolutions, increasing the system's sensitivity to the perturbation and allowing for a more detailed characterization of the quantum dynamics. ## Many-Body Interference and Signal Amplification * The researchers discovered that higher-order OTOCs function like many-body interferometers, where the quantum states of many particles interfere with one another. * The perturbation gates ($B$ and $M$) act as mirrors; when a resonance condition is met (where $U^\dagger$ is the exact inverse of $U$), constructive interference occurs. * This constructive interference amplifies specific quantum correlations, allowing the OTOC signal magnitude to scale as a negative power of the system size, rather than the exponential decay typically seen in chaotic systems. * This amplification makes the OTOC a sensitive instrument for identifying the specific correlations generated between two different qubits during the evolution of the circuit. ## Practical Applications and Future Research The success of the Quantum Echoes algorithm on the Willow chip marks a transition toward using quantum computers for tasks that are both beyond-classical and physically relevant. This method is particularly well-suited for Hamiltonian learning in Nuclear Magnetic Resonance (NMR) and studying the flow of electrons in high-temperature superconductors. Moving forward, the ability to measure verifiable expectation values in the chaotic regime will be essential for researchers looking to simulate complex quantum materials that are impossible to model on classical hardware.

quantum-algorithmsquantum-computingquantum-advantageout-of-time-order-correlators+3