We compare pseudopure state ensemble implementations, quantified by their initial polarization and ensemble size, of Grover's search algorithm to probabilistic classical sequential search algorithms in terms of their success and failure probabilities. We propose a criterion for quantifying the resources used by the ensemble implementation via the aggregate number of oracle invocations across the entire ensemble and use this as a basis for comparison with classical search algorithms. We determine bounds for a critical polarization such that the ensemble algorithm succeeds with a greater probability than the probabilistic classical sequential search. Our results indicate that the critical polarization scales as ${N}^{\ensuremath{-}1/4}$, where $N$ is the database size and that for typical room temperature solution state NMR, the polarization is such that the ensemble implementation of Grover's algorithm would be advantageous for $N\ensuremath{\gtrsim}{10}^{22}$.We compare pseudopure state ensemble implementations, quantified by their initial polarization and ensemble size, of Grover's search algorithm to probabilistic classical sequential search algorithms in terms of their success and failure probabilities. We propose a criterion for quantifying the resources used by the ensemble implementation via the aggregate number of oracle invocations across the entire ensemble and use this as a basis for comparison with classical search algorithms. We determine bounds for a critical polarization such that the ensemble algorithm succeeds with a greater probability than the probabilistic classical sequential search. Our results indicate that the critical polarization scales as ${N}^{\ensuremath{-}1/4}$, where $N$ is the database size and that for typical room temperature solution state NMR, the polarization is such that the ensemble implementation of Grover's algorithm would be advantageous for $N\ensuremath{\gtrsim}{10}^{22}$.

arXiv:0708.0808Physical Review AMay 13, 20081 citation

General approaches in ensemble quantum computing

V. Vimalan, Narayanan Chandrakumar

Journal of Chemical SciencesJan 1, 20082 citations

Improving the Reliability of Quantum Circuits by Evolving Heterogeneous Ensembles

Owain Parry, Clark, John, Phil McMinn

Quantum computers can perform certain operations exponentially faster than classical computers, but designing quantum circuits is challenging. To that end, researchers used evolutionary algorithms to produce probabilistic quantum circuits that give the correct output more often than not for any input. They can be executed multiple times, with the outputs combined using a classical method (such as voting) to produce the final output, effectively creating a homogeneous ensemble of circuits (i.e., all identical). Inspired by n-version programming and ensemble learning, we developed a tool that uses an evolutionary algorithm to generate heterogeneous ensembles of circuits (i.e., all different), named QuEEn. We used it to evolve ensembles to solve the Iris classification problem. When using ideal simulation, we found the performance of heterogeneous ensembles to be greater than that of homogeneous ensembles to a statistically significant degree. When using noisy simulation, we still observed a statistically significant improvement in the majority of cases. Our results indicate that evolving heterogeneous ensembles is an effective strategy for improving the reliability of quantum circuits. This is particularly relevant in the current NISQ era of quantum computing where computers do not yet have good tolerance to quantum noise.Quantum computers can perform certain operations exponentially faster than classical computers, but designing quantum circuits is challenging. To that end, researchers used evolutionary algorithms to produce probabilistic quantum circuits that give the correct output more often than not for any input. They can be executed multiple times, with the outputs combined using a classical method (such as voting) to produce the final output, effectively creating a homogeneous ensemble of circuits (i.e., all identical). Inspired by n-version programming and ensemble learning, we developed a tool that uses an evolutionary algorithm to generate heterogeneous ensembles of circuits (i.e., all different), named QuEEn. We used it to evolve ensembles to solve the Iris classification problem. When using ideal simulation, we found the performance of heterogeneous ensembles to be greater than that of homogeneous ensembles to a statistically significant degree. When using noisy simulation, we still observed a statistically significant improvement in the majority of cases. Our results indicate that evolving heterogeneous ensembles is an effective strategy for improving the reliability of quantum circuits. This is particularly relevant in the current NISQ era of quantum computing where computers do not yet have good tolerance to quantum noise.

arXiv:2409.09103Sep 13, 20241 citation

Algorithms on Ensemble Quantum Computers

P. Oscar Boykin, Tal Mor, Vwani Roychowdhury +1 more

In ensemble (or bulk) quantum computation, measurements of qubits in an individual computer cannot be performed. Instead, only expectation values can be measured. As a result of this limitation on the model of computation, various important algorithms cannot be processed directly on such computers, and must be modified. We provide modifications of various existing protocols, including algorithms for universal fault--tolerant computation, Shor's factorization algorithm (which can be extended to any algorithm computing an NP function), and some search algorithms to enable processing them on ensemble quantum computers.In ensemble (or bulk) quantum computation, measurements of qubits in an individual computer cannot be performed. Instead, only expectation values can be measured. As a result of this limitation on the model of computation, various important algorithms cannot be processed directly on such computers, and must be modified. We provide modifications of various existing protocols, including algorithms for universal fault--tolerant computation, Shor's factorization algorithm (which can be extended to any algorithm computing an NP function), and some search algorithms to enable processing them on ensemble quantum computers.

arXiv:quant-ph/9907067Jul 21, 19993 citations

Quantum Computer Search Algorithms: Can We Outperform the Classical Search Algorithms?

Avery M. Leider, Sadida Siddiqui, Daniel A. Sabol +1 more

Advances in intelligent systems and computingOct 12, 20195 citations

N

is the database size and that for typical room temperature solution state NMR, the polarization is such that the ensemble implementation of Grover's algorithm would be advantageous for $N\ensuremath{\gtrsim}{10}^{22}$.