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:2411.06822

Efficient Classical Computation of Single-Qubit Marginal Measurement Probabilities to Simulate Certain Classes of Quantum Algorithms

Santana Yuda Pradata, M 'Anin N. 'Azhiim, Hendry M. Lim, Suryanto, Wiwit, Ahmad R. T. Nugraha, Amrizal, Muhammad Alfian, Takizawa, Hiroyuki

Published Nov 11, 2024• 0 citations
arXivHTMLPDF

Abstract

Classical simulations of quantum circuits are essential for verifying and benchmarking quantum algorithms, particularly for large circuits, where computational demands increase exponentially with the number of qubits. Among available methods, the classical simulation of quantum circuits inspired by density functional theory -- the so-called QC-DFT method, shows promise for large circuit simulations as it approximates the quantum circuits using single-qubit reduced density matrices to model multi-qubit systems. However, the QC-DFT method performs very poorly when dealing with multi-qubit gates. In this work, we introduce a novel CNOT "functional" that leverages neural networks to generate unitary transformations, effectively mitigating the simulation errors observed in the original QC-DFT method. For random circuit simulations, our modified QC-DFT enables efficient computation of single-qubit marginal measurement probabilities, or single-qubit probability (SQPs), and achieves lower SQP errors and higher fidelities than the original QC-DFT method. Despite some limitations in capturing full entanglement and joint probability distributions, we find potential applications of SQPs in simulating Shor's and Grover's algorithms for specific solution classes. These findings advance the capabilities of classical simulations for some quantum problems and provide insights into managing entanglement and gate errors in practical quantum computing.

DOI
10.48550/arxiv.2411.06822

Related papers

Efficient Mean-Field Simulation of Quantum Circuits Inspired by Density Functional Theory

Marco Bernardi

Exact simulations of quantum circuits (QCs) are currently limited to ∼50 qubits because the memory and computational cost required to store the QC wave function scale exponentially with qubit number. Therefore, developing efficient schemes for approximate QC simulations is a current research focus. Here, we show simulations of QCs with a method inspired by density functional theory (DFT), a widely used approach for studying many-electron systems. Our calculations can predict marginal single-qubit probabilities (SQPs) with over 90% accuracy in several classes of QCs with universal gate sets, using memory and computational resources linear in qubit number despite the formal exponential cost of the SQPs. This is achieved by developing a mean-field description of QCs and formulating optimal single- and two-qubit gate functionals─analogues of exchange-correlation functionals in DFT─to evolve the SQPs without computing the QC wave function. Current limitations and future extensions of this formalism are discussed.

arXiv:2210.16465•Journal of Chemical Theory and Computation•Nov 10, 2023•2 citations

Deep Learning-Integrated Pairwise-Qubit Subsystems for Highly Efficient Quantum Circuit Simulation

Santana Yuda Pradata, Muhammad Alfian Amrizal, Wiwit Suryanto +2 more

Classically simulating large quantum circuits is well-known to be difficult due to its exponential scaling O(2n) in computations and memory with respect to the number of qubits (n). We propose a novel classical simulation framework for quantum circuits, combining pairwise-qubit subsystems (PQS) with deep learning, thus called PQS simulation, to achieve scalable and highly efficient circuit evaluation. By representing quantum states as sequences of reduced density matrices and modeling two-qubit interactions through learnable unitary operators, this representation yields quadratic space and linear time per elementary gate, i.e., O(n2) memory and O(n) time per-gate update. A custom multi-hidden long short-term memory architecture is trained to learn and predict the evolution of pairwise entangled qubit subsystems. We demonstrate the applicability of the method to Shor period-finding circuits in the special case where the period is a power-of-two, for which the ideal circuit yields a unique outcome and the period can be inferred from single-qubit measurement probabilities. Despite being trained on smaller circuits, the model generalizes to higher qubit counts than those required during training, achieving success probabilities up to 35.48% on the 18-qubit circuit, while simultaneously offering significant run-time advantages over exact simulation (up to 66 times faster on the 24-qubit circuit). Because Shor’s classical post-processing is cheap, we can wrap PQS simulation in an error-tolerant loop for these circuit instances, which results in an expected runtime of O(n4/(1 − ε)), where 1 − ε is the probability that PQS simulation returns the correct period. For comparisons, we provide FLOP/s-normalized projections: our measured 36-qubit Quantum Fourier Transform runtime projects to 0.158 s on a single Argonne Theta node (versus a reported 78.98 h), and 40-qubit Shor projects to 19.3 s on a 2,048-A100 cluster (versus ∼ 200 s). We also analyze failure modes via the distribution of single-qubit measurement probabilities and find errors concentrated in the lowest index qubit, suggesting that targeted mitigation on only a few qubits may suffice. The PQS simulation exhibits a promising direction for approximate, flexible, and scalable simulation of quantum algorithms on classical hardware.

International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia)•Jan 9, 2026•0 citations

Probabilistic Simulation of Quantum Circuits with Neural Network Approximations

Jincheng Zhang

The simulation of quantum circuits presents a significant bottleneck in the development and understanding of quantum algorithms. Traditional methods relying on the full wave function description quickly become computationally intractable as the number of qubits and circuit depth increases. This work proposes a novel approach utilizing neural networks to approximate the probabilities of measurement outcomes within a quantum circuit. The core idea is to train a neural network to learn the complex dynamics of quantum evolution, thereby enabling efficient simulation with a significantly reduced parameter space. We introduce a framework that maps the quantum circuit to a neural network architecture, allowing for approximate but tractable simulation. The effectiveness of this approach is demonstrated through theoretical analysis and a conceptual implementation strategy, highlighting its potential to unlock the exploration of complex quantum algorithms and accelerate the development of quantum computing. The primary objective is to provide a computationally feasible alternative to traditional simulation techniques, bridging the gap between theoretical quantum algorithm design and practical implementation. The key innovation lies in leveraging the representational power of neural networks to capture the essential correlations inherent in quantum systems.

•Sep 2, 2026•0 citations

Simulating quantum computers with probabilistic methods

Maarten Van den Nest

We investigate the boundary between classical and quantum computational power. This work consists of two parts. First we develop new classical simulation algorithms that are centered on sampling methods. Using these techniques we generate new classes of classically simulatable quantum circuits where standard techniques relying on the exact computation of measurement probabilities fail to provide efficient simulations. For example, we show how various concatenations of matchgate, Toffoli, Clifford, bounded-depth, Fourier transform and other circuits are classically simulatable. We also prove that sparse quantum circuits as well as circuits composed of CNOT and $\exp[{i\theta X}]$ gates can be simulated classically. In a second part, we apply our results to the simulation of quantum algorithms. It is shown that a recent quantum algorithm, concerned with the estimation of Potts model partition functions, can be simulated efficiently classically. Finally, we show that the exponential speed-ups of Simon's and Shor's algorithms crucially depend on the very last stage in these algorithms, dealing with the classical postprocessing of the measurement outcomes. Specifically, we prove that both algorithms would be classically simulatable if the function classically computed in this step had a sufficiently peaked Fourier spectrum.

Quantum Information and Computation•Sep 1, 2011•55 citations

Simulating quantum computers with probabilistic methods

M. Van den Nest

We investigate the boundary between classical and quantum computational power. This work consists of two parts. First we develop new classical simulation algorithms that are centered on sampling methods. Using these techniques we generate new classes of classically simulatable quantum circuits where standard techniques relying on the exact computation of measurement probabilities fail to provide efficient simulations. For example, we show how various concatenations of matchgate, Toffoli, Clifford, bounded-depth, Fourier transform and other circuits are classically simulatable. We also prove that sparse quantum circuits as well as circuits composed of CNOT and exp[iaX] gates can be simulated classically. In a second part, we apply our results to the simulation of quantum algorithms. It is shown that a recent quantum algorithm, concerned with the estimation of Potts model partition functions, can be simulated efficiently classically. Finally, we show that the exponential speed-ups of Simon's and Shor's algorithms crucially depend on the very last stage in these algorithms, dealing with the classical postprocessing of the measurement outcomes. Specifically, we prove that both algorithms would be classically simulatable if the function classically computed in this step had a sufficiently peaked Fourier spectrum.

arXiv:0911.1624•Nov 9, 2009•3 citations

Implementing arbitrary quantum operations via quantum walks on a cycle graph

Jia-Yi Lin, Xinyu Li, Yu-Hao Shao +2 more

The quantum circuit model is the most commonly used model for implementing quantum computers and quantum neural networks whose essential tasks are to realize certain unitary operations. The circuit model usually implements a desired unitary operation $U(N)$ by a sequence of single-qubit and two-qubit unitary gates from a universal set. Although this certainly facilitates the experimentalists as they only need to prepare several different kinds of universal gates, the number of gates required to implement an arbitrary desired unitary operation is usually large. Hence, the efficiency in terms of the circuit depth or running time is not guaranteed. Here we propose an alternative approach; we use a simple discrete-time quantum walk (DTQW) on a cycle graph to model an arbitrary unitary operation $U(N)$ without the need to decompose it into a sequence of gates of smaller sizes. Our model is essentially a quantum neural network based on DTQW. Firstly, it is universal as we show that any unitary operation $U(N)$ can be realized via an appropriate choice of coin operators. Secondly, our DTQW-based neural network can be updated efficiently via a learning algorithm, i.e., a modified stochastic gradient descent algorithm adapted to our network. By training this network, one can promisingly find approximations to arbitrary desired unitary operations. With an additional measurement on the output, the DTQW-based neural network can also implement general positive-operator-valued measure (POVM) measurements. We show its capacity in implementing arbitrary two-outcome POVMs via numeric simulation. We further demonstrate that the network can be simplified and can overcome device noises during the training so that it becomes more friendly for laboratory implementations. Our work shows the capability of the DTQW-based neural network in quantum computation and its potential in laboratory implementations.

arXiv:2210.14450•Physical Review A•Apr 5, 2023•5 citations
Classical simulations of quantum circuits are essential for verifying and benchmarking quantum algorithms, particularly for large circuits, where computational demands increase exponentially with the number of qubits. Among available methods, the classical simulation of quantum circuits inspired by density functional theory -- the so-called QC-DFT method, shows promise for large circuit simulations as it approximates the quantum circuits using single-qubit reduced density matrices to model multi-qubit systems. However, the QC-DFT method performs very poorly when dealing with multi-qubit gates. In this work, we introduce a novel CNOT "functional" that leverages neural networks to generate unitary transformations, effectively mitigating the simulation errors observed in the original QC-DFT method. For random circuit simulations, our modified QC-DFT enables efficient computation of single-qubit marginal measurement probabilities, or single-qubit probability (SQPs), and achieves lower SQP errors and higher fidelities than the original QC-DFT method. Despite some limitations in capturing full entanglement and joint probability distributions, we find potential applications of SQPs in simulating Shor's and Grover's algorithms for specific solution classes. These findings advance the capabilities of classical simulations for some quantum problems and provide insights into managing entanglement and gate errors in practical quantum computing.
Exact simulations of quantum circuits (QCs) are currently limited to ∼50 qubits because the memory and computational cost required to store the QC wave function scale exponentially with qubit number. Therefore, developing efficient schemes for approximate QC simulations is a current research focus. Here, we show simulations of QCs with a method inspired by density functional theory (DFT), a widely used approach for studying many-electron systems. Our calculations can predict marginal single-qubit probabilities (SQPs) with over 90% accuracy in several classes of QCs with universal gate sets, using memory and computational resources linear in qubit number despite the formal exponential cost of the SQPs. This is achieved by developing a mean-field description of QCs and formulating optimal single- and two-qubit gate functionals─analogues of exchange-correlation functionals in DFT─to evolve the SQPs without computing the QC wave function. Current limitations and future extensions of this formalism are discussed.
Classically simulating large quantum circuits is well-known to be difficult due to its exponential scaling O(2n) in computations and memory with respect to the number of qubits (n). We propose a novel classical simulation framework for quantum circuits, combining pairwise-qubit subsystems (PQS) with deep learning, thus called PQS simulation, to achieve scalable and highly efficient circuit evaluation. By representing quantum states as sequences of reduced density matrices and modeling two-qubit interactions through learnable unitary operators, this representation yields quadratic space and linear time per elementary gate, i.e., O(n2) memory and O(n) time per-gate update. A custom multi-hidden long short-term memory architecture is trained to learn and predict the evolution of pairwise entangled qubit subsystems. We demonstrate the applicability of the method to Shor period-finding circuits in the special case where the period is a power-of-two, for which the ideal circuit yields a unique outcome and the period can be inferred from single-qubit measurement probabilities. Despite being trained on smaller circuits, the model generalizes to higher qubit counts than those required during training, achieving success probabilities up to 35.48% on the 18-qubit circuit, while simultaneously offering significant run-time advantages over exact simulation (up to 66 times faster on the 24-qubit circuit). Because Shor’s classical post-processing is cheap, we can wrap PQS simulation in an error-tolerant loop for these circuit instances, which results in an expected runtime of O(n4/(1 − ε)), where 1 − ε is the probability that PQS simulation returns the correct period. For comparisons, we provide FLOP/s-normalized projections: our measured 36-qubit Quantum Fourier Transform runtime projects to 0.158 s on a single Argonne Theta node (versus a reported 78.98 h), and 40-qubit Shor projects to 19.3 s on a 2,048-A100 cluster (versus ∼ 200 s). We also analyze failure modes via the distribution of single-qubit measurement probabilities and find errors concentrated in the lowest index qubit, suggesting that targeted mitigation on only a few qubits may suffice. The PQS simulation exhibits a promising direction for approximate, flexible, and scalable simulation of quantum algorithms on classical hardware.
The simulation of quantum circuits presents a significant bottleneck in the development and understanding of quantum algorithms. Traditional methods relying on the full wave function description quickly become computationally intractable as the number of qubits and circuit depth increases. This work proposes a novel approach utilizing neural networks to approximate the probabilities of measurement outcomes within a quantum circuit. The core idea is to train a neural network to learn the complex dynamics of quantum evolution, thereby enabling efficient simulation with a significantly reduced parameter space. We introduce a framework that maps the quantum circuit to a neural network architecture, allowing for approximate but tractable simulation. The effectiveness of this approach is demonstrated through theoretical analysis and a conceptual implementation strategy, highlighting its potential to unlock the exploration of complex quantum algorithms and accelerate the development of quantum computing. The primary objective is to provide a computationally feasible alternative to traditional simulation techniques, bridging the gap between theoretical quantum algorithm design and practical implementation. The key innovation lies in leveraging the representational power of neural networks to capture the essential correlations inherent in quantum systems.
We investigate the boundary between classical and quantum computational power. This work consists of two parts. First we develop new classical simulation algorithms that are centered on sampling methods. Using these techniques we generate new classes of classically simulatable quantum circuits where standard techniques relying on the exact computation of measurement probabilities fail to provide efficient simulations. For example, we show how various concatenations of matchgate, Toffoli, Clifford, bounded-depth, Fourier transform and other circuits are classically simulatable. We also prove that sparse quantum circuits as well as circuits composed of CNOT and exp⁡[iθX]\exp[{i\theta X}]exp[iθX] gates can be simulated classically. In a second part, we apply our results to the simulation of quantum algorithms. It is shown that a recent quantum algorithm, concerned with the estimation of Potts model partition functions, can be simulated efficiently classically. Finally, we show that the exponential speed-ups of Simon's and Shor's algorithms crucially depend on the very last stage in these algorithms, dealing with the classical postprocessing of the measurement outcomes. Specifically, we prove that both algorithms would be classically simulatable if the function classically computed in this step had a sufficiently peaked Fourier spectrum.
We investigate the boundary between classical and quantum computational power. This work consists of two parts. First we develop new classical simulation algorithms that are centered on sampling methods. Using these techniques we generate new classes of classically simulatable quantum circuits where standard techniques relying on the exact computation of measurement probabilities fail to provide efficient simulations. For example, we show how various concatenations of matchgate, Toffoli, Clifford, bounded-depth, Fourier transform and other circuits are classically simulatable. We also prove that sparse quantum circuits as well as circuits composed of CNOT and exp[iaX] gates can be simulated classically. In a second part, we apply our results to the simulation of quantum algorithms. It is shown that a recent quantum algorithm, concerned with the estimation of Potts model partition functions, can be simulated efficiently classically. Finally, we show that the exponential speed-ups of Simon's and Shor's algorithms crucially depend on the very last stage in these algorithms, dealing with the classical postprocessing of the measurement outcomes. Specifically, we prove that both algorithms would be classically simulatable if the function classically computed in this step had a sufficiently peaked Fourier spectrum.
The quantum circuit model is the most commonly used model for implementing quantum computers and quantum neural networks whose essential tasks are to realize certain unitary operations. The circuit model usually implements a desired unitary operation U(N)U(N)U(N) by a sequence of single-qubit and two-qubit unitary gates from a universal set. Although this certainly facilitates the experimentalists as they only need to prepare several different kinds of universal gates, the number of gates required to implement an arbitrary desired unitary operation is usually large. Hence, the efficiency in terms of the circuit depth or running time is not guaranteed. Here we propose an alternative approach; we use a simple discrete-time quantum walk (DTQW) on a cycle graph to model an arbitrary unitary operation U(N)U(N)U(N) without the need to decompose it into a sequence of gates of smaller sizes. Our model is essentially a quantum neural network based on DTQW. Firstly, it is universal as we show that any unitary operation U(N)U(N)U(N) can be realized via an appropriate choice of coin operators. Secondly, our DTQW-based neural network can be updated efficiently via a learning algorithm, i.e., a modified stochastic gradient descent algorithm adapted to our network. By training this network, one can promisingly find approximations to arbitrary desired unitary operations. With an additional measurement on the output, the DTQW-based neural network can also implement general positive-operator-valued measure (POVM) measurements. We show its capacity in implementing arbitrary two-outcome POVMs via numeric simulation. We further demonstrate that the network can be simplified and can overcome device noises during the training so that it becomes more friendly for laboratory implementations. Our work shows the capability of the DTQW-based neural network in quantum computation and its potential in laboratory implementations.