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:2601.09128 · Science China Information Sciences

Distributed Exact Quantum Amplitude Amplification Algorithm for Arbitrary Quantum States

Xu Zhou, Wenxuan Tao, Keren Li, Shenggen Zheng

quant-phSubmitted Jan 14, 2026• Announced Jan 15, 2026• 0 citations
arXivHTMLPDF

Abstract

In the noisy intermediate-scale quantum (NISQ) era, distributed quantum computation has garnered considerable interest, as it overcomes the physical limitations of single-device architectures and enables scalable quantum information processing. In this study, we focus on the challenge of achieving exact amplitude amplification for quantum states with arbitrary amplitude distributions and subsequently propose a Distributed Exact Quantum Amplitude Amplification Algorithm (DEQAAA). Specifically, (1) it supports partitioning across any number of nodes $t$ within the range $2 \leq t \leq n$; (2) the maximum qubit count required for any single node is expressed as $\max \left(n_0,n_1,\dots,n_{t-1} \right) $, where $n_j$ represents the number of qubits at the $j$-th node, with $\sum_{j=0}^{t-1} n_j =n$; (3) it can realize exact amplitude amplification for multiple targets of a quantum state with arbitrary amplitude distributions; (4) we verify the effectiveness of DEQAAA by resolving a specific exact amplitude amplification task involving two targets (8 and 14 in decimal) via MindSpore Quantum, a quantum simulation software, with tests conducted on 4-qubit, 6-qubit, 8-qubit and 10-qubit systems. Notably, through the decomposition of $C^{n-1}PS$ gates, DEQAAA demonstrates remarkable advantages in both quantum gate count and circuit depth as the qubit number scales, thereby boosting its noise resilience. In the 10-qubit scenario, for instance, it achieves a reduction of over $97\%$ in both indicators compared to QAAA and EQAAA, underscoring its outstanding resource-saving performance.

Journal reference
SCIENCE CHINA Information Sciences, 2026
DOI
10.1007/s11432-026-5020-7
Comments
42 pages, 27 figures, comments are welcome

Related papers

Modular Quantum Amplitude Estimation: A Scalable and Adaptive Framework

Alok Shukla, Prakash Vedula

Quantum Amplitude Estimation (QAE) is a key primitive in quantum computing, but its standard implementation using Quantum Phase Estimation is resource-intensive, requiring a large number of coherent qubits in a single circuit block to achieve high precision. This presents a significant challenge for near-term Noisy Intermediate-Scale Quantum (NISQ) devices. To address this, we introduce the Adaptive Windowed Quantum Amplitude Estimation (AWQAE) framework, a modular, scalable and adaptive approach that decouples estimation precision from the number of physical qubits required in a single circuit. AWQAE operates by iteratively estimating the phase bits in small, fixed-size chunks, using a number of smaller, independent quantum circuits, which are amenable to parallel processing. A key technical contribution of this work is introduction of a phase resolution circuit and an ancilla-guided mechanism that enables accurate chunk assignment and eigenphase reconstruction in the presence of multiple eigenstates. This design is inherently NISQ-friendly, by lowering circuit depth and qubit count per block to reduce decoherence and noise effects. A key component of our approach is a robust classical post-processing algorithm that resolves measurement ambiguities that arise during the iterative process. This post-processing routine uses a least-significant-bit (LSB)-to-most-significant-bit (MSB) correction to reconstruct the full, high-precision phase estimate, ensuring accuracy. By combining a modular quantum-classical loop with an ambiguity-aware reconstruction method, AWQAE offers a powerful and flexible solution for performing high-precision QAE on resource-constrained quantum hardware. Our approach demonstrates enhanced scalability, and adaptability, making it a promising candidate for practical applications of QAE in the NISQ era.

arXiv:2508.05805•Aug 7, 2025•3 citations

Quantum Circuit Design for Finding k-Cliques via Quantum Amplitude Amplification Strategies

Simone Perriello

The 𝑘-clique problem, which involves identifying complete subgraphs of size 𝑘 within a graph, is a fundamental challenge in combinatorial optimization with applications in network analysis, bioinformatics, and cryptography.As the number of nodes 𝑛 grows, classical algorithms become computationally intractable, motivating the exploration of quantum computing to address these limitations.This work introduces two quantum algorithms for solving the 𝑘-clique problem: one based on Quantum Amplitude Amplification (QAA) and another leveraging Quantum Walks (QW) over the Johnson graph 𝐽 (𝑛, 𝑘).By exploiting the regular structure of the Johnson graph, the QW approach achieves the same quadratic speedup of the QAA approach over classical algorithms, while remaining applicable to arbitrary undirected, unweighted graphs.We provide detailed quantum circuit designs for both approaches, analyzing their performance in terms of qubit count, gate count, and circuit depth under the NOT-CNOT-Toffoli + arbitrary rotations and Clifford + T gate sets.Compared to state-of-the-art quantum algorithms, our methods achieve significant improvements in scaling, particularly for dense graphs, with speedups ranging from 2 5 to 2 20 .

ACM International Conference on Computing Frontiers (CF)•May 28, 2025•3 citations

A Depolarizing Noise-aware Transpiler for Optimal Amplitude Amplification

Debashis Ganguly, Ahn, Wonsun

Amplitude amplification provides a quadratic speed-up for an array of quantum algorithms when run on a quantum machine perfectly isolated from its environment. However, the advantage is substantially diminished as the NISQ-era quantum machines lack the large number of qubits necessary to provide error correction. Noise in the computation grows with the number of gate counts in the circuit with each iteration of amplitude amplification. After a certain number of amplifications, the loss in accuracy from the gate noise starts to overshadow the gain in accuracy due to amplification, forming an inflection point. Beyond this point, accuracy continues to deteriorate until the machine reaches a maximally mixed state where the result is uniformly random. Hence, quantum transpilers should take the noise parameters of the underlying quantum machine into consideration such that the circuit can be optimized to attain the maximal accuracy possible for that machine. In this work, we propose an extension to the transpiler that predicts the accuracy of the result at every amplification with high fidelity by applying pure Bayesian analysis to individual gate noise rates. Using this information, it finds the inflection point and optimizes the circuit by halting amplification at that point. The prediction is made without needing to execute the circuit either on a quantum simulator or an actual quantum machine.

arXiv:2210.14335•Oct 25, 2022•0 citations

Distributed Quantum Algorithm for the NISQ Era: A Novel Approach to Solving Simon's Problem with Reduced Resources

Xu Zhou, Yuchen Wang, Wenxuan Tao +2 more

Abstract Distributed quantum computation has gained significant interest in the noisy intermediate‐scale quantum (NISQ) era. This paradigm requires each computing node to possess a reduced number of qubits and quantum gates. In this study, a Distributed Simon's Algorithm (DSA) is designed to tackle Simon's problem, which entails the discovery of a hidden string of a promised Boolean function , where if and only if or . Specifically, 1) our algorithm is capable of being partitioned into any nodes, where ; 2) the number of queries required by the DSA is , while that of the original Simon's algorithm (SA) is ; 3) the maximum number of qubits required by our approach at a single node is , which is fewer than the qubits required by both the SA and existing distributed Simon's algorithm. Here, denotes the number of computing qubits needed for the ‐th node and satisfies ; 4) the optimal circuit depth of the DSA is , which is reduced compared to the circuit depth of the SA, ; 5) in contrast to currently distributed schemes, the DSA eliminates the need for classical queries; 6) how the DSA solves a specific Simon's problem (e.g., ) is also simulated using MindSpore Quantum, a quantum simulation software. The simulation results show that the DSA features a shallower quantum circuit, thereby demonstrating enhanced resistance to circuit noise. This characteristic makes it more feasible for implementation in the NISQ era.

Advanced Quantum Technologies•Apr 13, 2025•2 citations

Heuristic Quantum Amplitude Amplification: A Traffic QUBO Case Study

Kip Nieman, Daniel Koch

Quantum Amplitude Amplification (QAA), the generalization of Grover's algorithm, is well-positioned for combinatorial optimization and is particularly promising for Quadratic Unconstrained Binary Optimization (QUBO) problems. QAA is appealing due to its ability to drive the quantum system to a target state, yielding the globally optimal solution with probability over $90$+%. However, realizing QAA for application-scale optimization currently exceeds quantum hardware capacity, which is further compounded by unresolved algorithmic challenges regarding the choice of free parameters. In this study, we address these issues by utilizing a realistic traffic flow QUBO problem to investigate the implementation of QAA as a heuristic solver. Specifically, allowing the diffusion operator parameter to take non-$π$ values expands the capabilities of QAA. This unlocks a new multiple-shot, low-iteration strategy that aims for a high cumulative probability rather than maximizing the probability of a single basis state. Using $25$-qubit simulations, our results demonstrate that heuristic QAA addresses two of the main challenges cited in previous studies. Firstly, heuristic QAA works even at a single iteration, reducing circuit depth by orders of magnitude compared to standard QAA. And secondly, we show that the problem-dependent parameters necessary for reaching optimal algorithmic performance can be reliably approximated with minimal upfront classical computing overhead.

quant-pharXiv:2609.13505•Sep 15, 2026•0 citations

A NISQ-Aware Hybrid Quantum-Classical Framework for Scalable Combinatorial Optimization

Haolong Ding, Mohan Wu, Yin Xu +1 more

Scalable combinatorial optimization under resource-constrained quantum hardware remains a fundamental challenge in the Noisy Intermediate-Scale Quantum (NISQ) era, due to the mismatch between exponentially growing solution spaces and limited quantum computational capacity. In this work, we propose a NISQ-aware hybrid quantum-classical optimization framework that reformulates large-scale combinatorial optimization as a resource-bounded distribution evolution process. Instead of directly optimizing individual solutions, the proposed framework operates on a probabilistic representation of the solution space, enabling efficient exploration under hardware constraints. Specifically, large problem instances are decomposed into qubit-compatible subproblems via clustering-based decomposition, ensuring resource-bounded optimization. Within each subproblem, a quantum genetic algorithm evolves the solution distribution, while periodically embedded amplitude amplification acts as a controlled quantum enhancement mechanism that accelerates convergence without increasing circuit depth. A classical refinement stage ensures global solution consistency. Extensive experiments on benchmark and synthetic datasets demonstrate that the proposed framework consistently outperforms classical and quantum-inspired baselines, with performance gains that become more pronounced as problem scale increases. This scale-dependent behavior indicates that scalability is achieved through structured decomposition rather than increased quantum complexity. Noise simulations further confirm robustness under realistic NISQ conditions, and ablation studies validate that both quantum evolutionary search and amplitude amplification contribute significantly to performance improvements.

quant-pharXiv:2606.00541•Jun 2, 2026•0 citations
In the noisy intermediate-scale quantum (NISQ) era, distributed quantum computation has garnered considerable interest, as it overcomes the physical limitations of single-device architectures and enables scalable quantum information processing. In this study, we focus on the challenge of achieving exact amplitude amplification for quantum states with arbitrary amplitude distributions and subsequently propose a Distributed Exact Quantum Amplitude Amplification Algorithm (DEQAAA). Specifically, (1) it supports partitioning across any number of nodes ttt within the range 2≤t≤n2 \leq t \leq n2≤t≤n; (2) the maximum qubit count required for any single node is expressed as max⁡(n0,n1,…,nt−1)\max \left(n_0,n_1,\dots,n_{t-1} \right) max(n0​,n1​,…,nt−1​), where njn_jnj​ represents the number of qubits at the jjj-th node, with ∑j=0t−1nj=n\sum_{j=0}^{t-1} n_j =n∑j=0t−1​nj​=n; (3) it can realize exact amplitude amplification for multiple targets of a quantum state with arbitrary amplitude distributions; (4) we verify the effectiveness of DEQAAA by resolving a specific exact amplitude amplification task involving two targets (8 and 14 in decimal) via MindSpore Quantum, a quantum simulation software, with tests conducted on 4-qubit, 6-qubit, 8-qubit and 10-qubit systems. Notably, through the decomposition of Cn−1PSC^{n-1}PSCn−1PS gates, DEQAAA demonstrates remarkable advantages in both quantum gate count and circuit depth as the qubit number scales, thereby boosting its noise resilience. In the 10-qubit scenario, for instance, it achieves a reduction of over 97%97\%97% in both indicators compared to QAAA and EQAAA, underscoring its outstanding resource-saving performance.
Quantum Amplitude Estimation (QAE) is a key primitive in quantum computing, but its standard implementation using Quantum Phase Estimation is resource-intensive, requiring a large number of coherent qubits in a single circuit block to achieve high precision. This presents a significant challenge for near-term Noisy Intermediate-Scale Quantum (NISQ) devices. To address this, we introduce the Adaptive Windowed Quantum Amplitude Estimation (AWQAE) framework, a modular, scalable and adaptive approach that decouples estimation precision from the number of physical qubits required in a single circuit. AWQAE operates by iteratively estimating the phase bits in small, fixed-size chunks, using a number of smaller, independent quantum circuits, which are amenable to parallel processing. A key technical contribution of this work is introduction of a phase resolution circuit and an ancilla-guided mechanism that enables accurate chunk assignment and eigenphase reconstruction in the presence of multiple eigenstates. This design is inherently NISQ-friendly, by lowering circuit depth and qubit count per block to reduce decoherence and noise effects. A key component of our approach is a robust classical post-processing algorithm that resolves measurement ambiguities that arise during the iterative process. This post-processing routine uses a least-significant-bit (LSB)-to-most-significant-bit (MSB) correction to reconstruct the full, high-precision phase estimate, ensuring accuracy. By combining a modular quantum-classical loop with an ambiguity-aware reconstruction method, AWQAE offers a powerful and flexible solution for performing high-precision QAE on resource-constrained quantum hardware. Our approach demonstrates enhanced scalability, and adaptability, making it a promising candidate for practical applications of QAE in the NISQ era.
The 𝑘-clique problem, which involves identifying complete subgraphs of size 𝑘 within a graph, is a fundamental challenge in combinatorial optimization with applications in network analysis, bioinformatics, and cryptography.As the number of nodes 𝑛 grows, classical algorithms become computationally intractable, motivating the exploration of quantum computing to address these limitations.This work introduces two quantum algorithms for solving the 𝑘-clique problem: one based on Quantum Amplitude Amplification (QAA) and another leveraging Quantum Walks (QW) over the Johnson graph 𝐽 (𝑛, 𝑘).By exploiting the regular structure of the Johnson graph, the QW approach achieves the same quadratic speedup of the QAA approach over classical algorithms, while remaining applicable to arbitrary undirected, unweighted graphs.We provide detailed quantum circuit designs for both approaches, analyzing their performance in terms of qubit count, gate count, and circuit depth under the NOT-CNOT-Toffoli + arbitrary rotations and Clifford + T gate sets.Compared to state-of-the-art quantum algorithms, our methods achieve significant improvements in scaling, particularly for dense graphs, with speedups ranging from 2 5 to 2 20 .
Amplitude amplification provides a quadratic speed-up for an array of quantum algorithms when run on a quantum machine perfectly isolated from its environment. However, the advantage is substantially diminished as the NISQ-era quantum machines lack the large number of qubits necessary to provide error correction. Noise in the computation grows with the number of gate counts in the circuit with each iteration of amplitude amplification. After a certain number of amplifications, the loss in accuracy from the gate noise starts to overshadow the gain in accuracy due to amplification, forming an inflection point. Beyond this point, accuracy continues to deteriorate until the machine reaches a maximally mixed state where the result is uniformly random. Hence, quantum transpilers should take the noise parameters of the underlying quantum machine into consideration such that the circuit can be optimized to attain the maximal accuracy possible for that machine. In this work, we propose an extension to the transpiler that predicts the accuracy of the result at every amplification with high fidelity by applying pure Bayesian analysis to individual gate noise rates. Using this information, it finds the inflection point and optimizes the circuit by halting amplification at that point. The prediction is made without needing to execute the circuit either on a quantum simulator or an actual quantum machine.
Abstract Distributed quantum computation has gained significant interest in the noisy intermediate‐scale quantum (NISQ) era. This paradigm requires each computing node to possess a reduced number of qubits and quantum gates. In this study, a Distributed Simon's Algorithm (DSA) is designed to tackle Simon's problem, which entails the discovery of a hidden string of a promised Boolean function , where if and only if or . Specifically, 1) our algorithm is capable of being partitioned into any nodes, where ; 2) the number of queries required by the DSA is , while that of the original Simon's algorithm (SA) is ; 3) the maximum number of qubits required by our approach at a single node is , which is fewer than the qubits required by both the SA and existing distributed Simon's algorithm. Here, denotes the number of computing qubits needed for the ‐th node and satisfies ; 4) the optimal circuit depth of the DSA is , which is reduced compared to the circuit depth of the SA, ; 5) in contrast to currently distributed schemes, the DSA eliminates the need for classical queries; 6) how the DSA solves a specific Simon's problem (e.g., ) is also simulated using MindSpore Quantum, a quantum simulation software. The simulation results show that the DSA features a shallower quantum circuit, thereby demonstrating enhanced resistance to circuit noise. This characteristic makes it more feasible for implementation in the NISQ era.
Quantum Amplitude Amplification (QAA), the generalization of Grover's algorithm, is well-positioned for combinatorial optimization and is particularly promising for Quadratic Unconstrained Binary Optimization (QUBO) problems. QAA is appealing due to its ability to drive the quantum system to a target state, yielding the globally optimal solution with probability over 909090+%. However, realizing QAA for application-scale optimization currently exceeds quantum hardware capacity, which is further compounded by unresolved algorithmic challenges regarding the choice of free parameters. In this study, we address these issues by utilizing a realistic traffic flow QUBO problem to investigate the implementation of QAA as a heuristic solver. Specifically, allowing the diffusion operator parameter to take non-πππ values expands the capabilities of QAA. This unlocks a new multiple-shot, low-iteration strategy that aims for a high cumulative probability rather than maximizing the probability of a single basis state. Using 252525-qubit simulations, our results demonstrate that heuristic QAA addresses two of the main challenges cited in previous studies. Firstly, heuristic QAA works even at a single iteration, reducing circuit depth by orders of magnitude compared to standard QAA. And secondly, we show that the problem-dependent parameters necessary for reaching optimal algorithmic performance can be reliably approximated with minimal upfront classical computing overhead.
Scalable combinatorial optimization under resource-constrained quantum hardware remains a fundamental challenge in the Noisy Intermediate-Scale Quantum (NISQ) era, due to the mismatch between exponentially growing solution spaces and limited quantum computational capacity. In this work, we propose a NISQ-aware hybrid quantum-classical optimization framework that reformulates large-scale combinatorial optimization as a resource-bounded distribution evolution process. Instead of directly optimizing individual solutions, the proposed framework operates on a probabilistic representation of the solution space, enabling efficient exploration under hardware constraints. Specifically, large problem instances are decomposed into qubit-compatible subproblems via clustering-based decomposition, ensuring resource-bounded optimization. Within each subproblem, a quantum genetic algorithm evolves the solution distribution, while periodically embedded amplitude amplification acts as a controlled quantum enhancement mechanism that accelerates convergence without increasing circuit depth. A classical refinement stage ensures global solution consistency. Extensive experiments on benchmark and synthetic datasets demonstrate that the proposed framework consistently outperforms classical and quantum-inspired baselines, with performance gains that become more pronounced as problem scale increases. This scale-dependent behavior indicates that scalability is achieved through structured decomposition rather than increased quantum complexity. Noise simulations further confirm robustness under realistic NISQ conditions, and ablation studies validate that both quantum evolutionary search and amplitude amplification contribute significantly to performance improvements.