Why the result of DDsim is removed?
Closed this issue · 16 comments
Is that because of the data structure of DDsim?
no, it's just because we have an update on the benchmark infras, and I haven't got time to reproduce the result of DDsim. But I'll update that hopefully by the end of this month.
I am confused because the result from DDsim and Qulacs would be different. The directly result we can get from DDsim is the tree-like data structure. There is a great overlap between a tree-like data structure and full amplitude list because of the transforming. Or this transforming already considered in your benchmarking?
I think this is in https://github.com/iic-jku/ddsim/blob/c04195be3a115524d93a1f5adbc754ad12e67d0a/apps/benchmark.cpp#L14
since ddsim is not using the same algorithm, we had a footnote in previous benchmark result report, and since I haven't reproduce all the results of ddsim myself, I can't say anything at this moment.
@Roger-luo Please let me know if I can help you with anything :)
@hillmich Hi! Can I have some comment on your BM result? Since the result DDsim got and other simulators got are different. For instance, DDsim returns a tree-like quantun state and Qulacs return a array-like quantum state. Both the transform from tree-like state to array-like state and the transform from array-like state to tree-like state would cause a running time gap. But in my opinion both data structure would have their advantages. The problem comes when we use X-Benchmarking or H-Benchmarking, is this fair since we start from the same point but end at different?
@DechinPhy I think comparing both approaches in the benchmark is fair if we don't hide that the approaches are different. You mentioned that both approaches have advantages (and disadvantages) and you are absolutely right. Applying a single gate is really easy with decision diagrams (DDs) but has noticable overhead (and, hence, runtime) with matrix-vector approaches. In contrast, the DDs take a really long time for the parameterized benchmark.
I find having these approaches in the same benchmark set with appropriate comments on the performace is tremendously helpful for users to get a good overview. What do you think?
@hillmich Sorry, I think it's just I've been quite busy in last few months, I think I need at least a full weekend to go through things myself to make sure they are correct. I'll try to finish this ASAP
@hillmich Even for DD diagram there are many kinds of representations, for example the Fig.2 in article Advanced Simulation of Quantum Computations show us two representations. And we should figure out that the running time will be totally different by using these two models. So it will be very confused when many kinds of tree-like BM shown in the results compare to array-like ones (It is ok for now because there are only one BM result is using tree-like data structure, but what if there comes another representations?).
So I just recomend that you to use algorithm benchmarking instead of circuit benchmarking. A simple example, just return an expectation value for QAOA or return an energy for VQE or return a factor number for Shor's algorithm. Such results would not make me confused. What do you think about it?
@DechinPhy Yeah, there are a few different types of decision diagrams. If more are added we could split the plots to have one for vector-based and one for decision diagram-based. Even better would be a github.io-page with interactive plots and additional explanations (although I'm afraid this will require quite some time to set up).
In my opinion, benchmarking algorithms instead of circuits would make sense as an addition. The algorithms you mentioned are more complex and have both quantum and conventional computing steps. This will also require some considerations on how to handle the random/measurement aspects. For example, Shor's algorithm can fail to factorize an number if the chosen coprime is not suitable. I'm not sure how we can ensure reproduciblity while still allowing some freedom for the simulators.
@Roger-luo No worries. Let me know if I can help you with anything.
@hillmich You are right there could be random aspects. Actually I would prefer to use QAOA or VQE as the test cases, which can return the same expectation value with given parameters. But even for Shor's algorithm there could be fair if you only count the time cost of quantum state preparation and sampling, even you sampled a wrong result. The point is that your result has the same meaning compared with the result from other simulators such as Qulacs. It is because you both got the sampled result from the same quantum state, and had nothing to do with tree-like or array-like data structure.
Actually even the plots are splitted for different kinds of DDs, there are still problems using circuit benchmarking. Such running time benchmarking can not convince others that the DD simulator will have a really better performance (For me I have many explorations toward DD simulator so I will trust your outstanding results, but it is not quite strict in theoratical). That is because of you got different kinds of tree-like quantum state. And it will cost you a lot of time to explain what is the different between all DD simulators.
So I would suggest you to underline the performing results with algorithm benchmarking rather than circuit benchmarking, unless you got results with the same theoratical meaning. Solve people's problems faster or better will always convince them, in a very short time. Only a suggestion, all depends on you, nice works you guys have been done :)
@DechinPhy You have a good point. I'm afraid it may take a while from my end to build the benchmark for the JKQ-DDSIM as I'm rather busy (and prior to that we should agree on which benchmarks we want to consider). @Roger-luo What do you think?
The parameterized circuit in this benchmark is already a quite common circuit for VQEs, we only evaluate the simulation time of the circuit without calculating expectation/measurements currently, this is already what you mentioned here. @DechinPhy I'm not sure about which circuit you are referring to. Or you mean we should include the timing of calculating the gradients etc.? However, that's more about the performance of the gradient, instead of simulation I believe.
If I understand correctly, for time-evolution like simulations, you just can't accelerate much with a structured amplitude since the entanglement entropy grows faster. (pls correct me if I'm wrong), thus I'm not sure about the benefit of using DD for QAOA, thus I don't see why DD will perform better than full amplitude simulation in QAOA.
@Roger-luo There are random aspects during the parameter optimization, which is, because of the implementation or usage of random algorithms. But this is not what we should focus on, since there are optimization algorithms without random aspects.
In the recent VQE or QAOA's algorithm framework, the most important point is how you can get the expectation value. For example, in a superconductor quantum chip you may run the same circuit time by time and get a set of binary strings. Thus you can estimate the state vector from the distribution of binary strings. After that you can estimate the expectation value since you known the hamiltonian and state vector. (Or you can estimate the expectation value from each binary string and sum over them term by term.)
What we are talking about is quantum simulators, which are used to simulate a quantum chip. So if we can evaluate the performance by sampling from the same quantum state would be strict in theoratical for me. But in most quantum simulators they store a full amplitude quantum state directly. Thus we can get the expectation value without sampling. This is not the algorithm framework of VQE or QAOA, it is about the new varational quantum algorithm framework proposed by Michael in article Training the Quantum Approximate Optimization Algorithm without access to a Quantum Processing Unit, which pointed out that we can use classical computer to get and optimize the expectation value instead of quantum chip and send a set of optimized parameter to quantum chip to get the final sampling results. This is why I think it is also reasonable to evaluate performance of simulators by getting expectation values.
What you mentioned that including optimization stuff will make sense if we can get the final final solution, for now we can only get the expectation value but it is not the final solution. In classical algorithm they will also evaluate the running time and the quality of solutions. Since we do not have the ability to give a solution, I don't think we need to include optimization stuff.
@hillmich And finally I should have a comment on DD simulator. DD is an algorithm framework rather than a software for me. By using DD's framework the quantum state is stored using less space, the calculation of matrix production can be represented by pointer swap and these are potentials DD got. So I think the DD would perform better with proper software optimization.
@DechinPhy I'm not sure about what you mean as for this benchmark, do you mean we should provide a benchmark that includes calculating the expectation/measurement where DD might work better for certain quantum algorithm simulation? Or a single instruction benchmark of sampling? Would you mind pointing out which kind of algorithm/circuit that is different from the current ones that we should implement? Thanks!
@Roger-luo My point is nothing more than that we should get the same results in one benchmarking, for all circuit types. You can't run 50m and claim that you get the championship in a 100m race, can you?
@DechinPhy to implement a benchmark you need to show people what exactly we need to benchmark if you think the current benchmark is not fair to DDSim rather than a vague metaphor. I'm closing this if there is no concrete suggestion on this, please feel free to submit a PR for new benchmark tasks.