Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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
