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•0 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•2 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

Deterministic, scalable, and entanglement efficient initialization of arbitrary quantum states

Prithvi Gundlapalli, Junyi Lee

Quantum computing promises to provide exponential speed-ups to certain classes of problems. In many such quantum algorithms, a classical vector $\mathbf{b}$ is encoded in the amplitudes of a quantum state $| b\rangle$. However, efficient amplitude encoding of an arbitrary vector $\mathbf{b}$ in $| b \rangle$ is known to be a difficult problem that can reverse the gains of such algorithms. More importantly, an arbitrary quantum state of $Q$ qubits generally requires $\sim 2^Q$ number of entangling gates, which is problematic for today's Noisy-Intermediate Scale Quantum (NISQ) computers where large numbers of such error-prone gates will result in significant decoherence before initialization is completed. In this work, we demonstrate a deterministic and scalable initialization algorithm that allows for states with low entanglement to be initialized on actual quantum computers with more than an order of magnitude less entangling gates and significantly shallower circuits as compared to isometric decomposition. For states with higher entanglement, optimally approximate states with lower entanglement may be found and initialized with similar performance. We show this to be true for various cases of interest such as the normal and log-normal distributions. Unlike variational approaches, our method requires no classical optimizations in high dimensional spaces and is not plagued with exponentially vanishing gradients or a multitude of local minimas.

•Oct 26, 2021•3 citations

A flexible high-performance simulator for the verification and benchmarking of quantum circuits implemented on real hardware

Benjamin Villalonga, Sergio Boixo, Bron C. Nelson +4 more

Here we present a flexible tensor network based simulator for quantum circuits on different topologies, including the Google Bristlecone QPU. Our simulator can compute both exact amplitudes, a task essential for the verification of the quantum hardware, as well as low-fidelity amplitudes to mimic Noisy Intermediate-Scale Quantum (NISQ) devices. While our simulator can be used to compute amplitudes of arbitrary quantum circuits, we focus on random quantum circuits (RQCs) [Boixo et al., Nature Physics 14] in the range of sizes expected for supremacy experiments. Our simulator enables the simulation of sampling on quantum circuits that were out of reach for previous approaches. For instance, our simulator is able to output single amplitudes with depth 1+32+1 for the full Bristlecone QPU in less than $(f \cdot 4200)$ hours on a single core, where $0<f\leq1$ is the target fidelity, on $2\times20$-core Intel Xeon Gold 6148 processors (Skylake). We also estimate that computing $10^6$ amplitudes (with fidelity 0.50\%) needed to sample from the full Bristlecone QPU with depth (1+32+1) would require about 3.5 days using the NASA Pleiades and Electra supercomputers combined. In addition, we discuss the hardness of the classical simulation of RQCs, as well as give evidence for the higher complexity in the simulation of Bristlecone topology as compared to other two-dimensional grids with the same number of qubits. Our analysis is supported by extensive simulations on NASA HPC clusters Pleiades and Electra. For the most computationally demanding simulation we had, namely the simulation of a $60$-qubit sub-lattice of Bristlecone, the two HPC clusters combined reached a peak of 20 PFLOPS (single precision), that is $64\%$ of their maximum achievable performance. To date, this numerical computation is the largest in terms of sustained PFLOPS and number of nodes utilized ever run on NASA HPC clusters.

•Nov 23, 2018•11 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
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.
Quantum computing promises to provide exponential speed-ups to certain classes of problems. In many such quantum algorithms, a classical vector b\mathbf{b}b is encoded in the amplitudes of a quantum state ∣b⟩| b\rangle∣b⟩. However, efficient amplitude encoding of an arbitrary vector b\mathbf{b}b in ∣b⟩| b \rangle∣b⟩ is known to be a difficult problem that can reverse the gains of such algorithms. More importantly, an arbitrary quantum state of QQQ qubits generally requires ∼2Q\sim 2^Q∼2Q number of entangling gates, which is problematic for today's Noisy-Intermediate Scale Quantum (NISQ) computers where large numbers of such error-prone gates will result in significant decoherence before initialization is completed. In this work, we demonstrate a deterministic and scalable initialization algorithm that allows for states with low entanglement to be initialized on actual quantum computers with more than an order of magnitude less entangling gates and significantly shallower circuits as compared to isometric decomposition. For states with higher entanglement, optimally approximate states with lower entanglement may be found and initialized with similar performance. We show this to be true for various cases of interest such as the normal and log-normal distributions. Unlike variational approaches, our method requires no classical optimizations in high dimensional spaces and is not plagued with exponentially vanishing gradients or a multitude of local minimas.
Here we present a flexible tensor network based simulator for quantum circuits on different topologies, including the Google Bristlecone QPU. Our simulator can compute both exact amplitudes, a task essential for the verification of the quantum hardware, as well as low-fidelity amplitudes to mimic Noisy Intermediate-Scale Quantum (NISQ) devices. While our simulator can be used to compute amplitudes of arbitrary quantum circuits, we focus on random quantum circuits (RQCs) [Boixo et al., Nature Physics 14] in the range of sizes expected for supremacy experiments. Our simulator enables the simulation of sampling on quantum circuits that were out of reach for previous approaches. For instance, our simulator is able to output single amplitudes with depth 1+32+1 for the full Bristlecone QPU in less than (f⋅4200)(f \cdot 4200)(f⋅4200) hours on a single core, where 0<f≤10<f\leq10<f≤1 is the target fidelity, on 2×202\times202×20-core Intel Xeon Gold 6148 processors (Skylake). We also estimate that computing 10610^6106 amplitudes (with fidelity 0.50\%) needed to sample from the full Bristlecone QPU with depth (1+32+1) would require about 3.5 days using the NASA Pleiades and Electra supercomputers combined. In addition, we discuss the hardness of the classical simulation of RQCs, as well as give evidence for the higher complexity in the simulation of Bristlecone topology as compared to other two-dimensional grids with the same number of qubits. Our analysis is supported by extensive simulations on NASA HPC clusters Pleiades and Electra. For the most computationally demanding simulation we had, namely the simulation of a 606060-qubit sub-lattice of Bristlecone, the two HPC clusters combined reached a peak of 20 PFLOPS (single precision), that is 64%64\%64% of their maximum achievable performance. To date, this numerical computation is the largest in terms of sustained PFLOPS and number of nodes utilized ever run on NASA HPC clusters.
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.