Efficient Contraction Order Statevector Simulator

[masa10-f]

Is your feature request related to a problem? Please describe.

The state vector simulator for MBQC inherently exhibits slower performance compared to that for quantum circuits, primarily attributed to two key factors:

1. MBQC necessitates the utilization of at least one ancillary qubit to proceed computation. This leads to at least a twofold increase in memory consumption, consequently extending the computational time.
2. In contrast to a gate in a quantum circuit, a single step in MBQC cannot encompass all single-qubit Unitary operations without changing the graph structure. This characteristic augments the size of the computational graph, demanding a higher computational load.

In order to address the aforementioned challenges, Graphix incorporates a minimize_space method designed to mitigate the impact of ancillary qubits on computational efficiency. This method aims to minimize the number of ancillary qubits required simultaneously, enabling Graphix to simulate large-scale MBQC with a comparatively lower computational burden.

However, it is important to note that this approach is constrained to simulating measurement patterns in standardized or NEMC forms, which are prevalent in MBQC. Additionally, it's crucial to acknowledge that the current implementation of the minimize_space method is heuristic. Consequently, it does not guarantee optimal outcomes in all cases, as it may not consistently yield the most efficient solutions.

Describe the feature you'd like A clear and concise description of what you want to happen.

I propose the implementation of a new simulator backend, the Contraction-wise State Vector Simulator(CW-SVS), into Graphix. The CW-SVS optimizes contraction order by delaying the calculation of outer products until the latest possible stage, leading to a substantial reduction in FLOPs. Importantly, this simulator maintains the same computational capabilities as conventional state vector simulators, as both calculate the same tensor network. The difference is just in contraction order.

The CW-SVS's intelligent contraction order incorporates the minimize_space feature of the Pattern class. This eliminates the need to explicitly consider the order of measurement patterns, enabling the seamless simulation of standardized measurement patterns. We can implement this backend with quimb and slightly modify the current tensornetwork backend.

Furthermore, applying this contraction-wise strategy could extend beyond the state vector simulator. It can be leveraged to enhance density matrix backends and circuit simulators, contributing to a more efficient and versatile computational framework.

Additional context Add any other context or screenshots about the feature request here.

na

[shinich1]

Nice!

A minor point but what's the reasoning for the name 'contraction-wise simulation'? this '-wise' sounds a bit like doing simulation for every contraction?

Perhaps something like:

• tensor-based state vector simulation
• path-flexible state vector simulation etc?

[masa10-f]

@shinich1 Thank you for your comment! tensor-based is not what I mean here because the conventional state vector simulator is also a 'tensor-based' simulator. I wanna express 'perform contraction in clever or smart way' as the only difference is in a contraction order. So, contraction-smart or contraction-clever? What do you think about these?

[shinich1]

Indeed conventional sv sim is also tensor-based and as you say, the difference is the increased flexibility of the contraction path. clever or smart may not be a good word for class/method name, let me think of a wording for this

[masa10-f]

How about "Efficient Contraction Order(ECO) Statevector Simulator"? @shinich1 (ChatGPT suggests this name and it sounds nice to me:))

[shinich1]

@masa10-f sounds good to me!