This new algorithm for QC calculation was introduced recently (2017 4Q) by IBM/ Pednault et al. to great fanfare. The paper seems more couched in the language of physics.

Are there any basic overview/analyses of this by computer scientists about the general "design pattern" utilized, vs the prior algorithmic techniques for the problem, or can someone provide one? What about the complexity analysis of the techniques?

"Breaking the 49-Qubit Barrier in the Simulation of Quantum Circuits"


From a computer science perspective, the calculation of quantum-state amplitudes can be related to group-by aggregation queries in relational database systems, and the techniques we developed to reorganize calculations can be related to algebraic manipulations that are performed by database query optimizers. The general “design pattern” is thus analogous: convert quantum circuits into graph-based algebraic representations that can be readily manipulated and then use those representations to generate optimized execution plans for their simulation. A complexity analysis could then be approached from this perspective.

I included a simple example in a reply to a question posted on the IBM Q Experience Forum: Equations for Bristle Brush Example

|improve this answer|||||

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.