Implement Grover's Algorithm using Lightning-Qubit's C++ API

[tomlqc]

Important Note

⚠️ This issue is part of an internal assignment and not meant for external contributors

Context

Lightning-Qubit is one of the C++ simulators for PennyLane. It uses Python bindings to be integrated in PennyLane's Python-API. Alternatively, algorithms can be implemented with the C++ API directly. The purpose of this issue is to build Grover's algorithm in C++ only and to benchmark it against an implementation with PennyLane.

Requirements

• Create a standalone C++ executable or use the testing infrastructure in Lightning-Qubit to implement Grover's algorithm in C++.
• Create a pull-request in the PennyLane Lightning repository and complete the steps listed in the PR template that make sense for this issue.
• Build a similar algorithm with PennyLane, benchmark with your C++ implementation and highlight the differences and upload the results to the pull-request for further discussions.
• Mark the PR ready for review.

Don't hesitate to ask for clarification or raise any concerns regarding the issue. We'll be happy to discuss with you!

[jzaia18]

Hi Thomas, thanks for giving me the opportunity to work on this! I had some questions about setting everything up such that I can build files against the C++ API. I couldn't find instructions on how to do this anywhere in the repository or on the pennylane main site. I was able to build and run the C++ files using make test-cpp (and all tests pass) but I wasn't sure where to find the files for including/linking when I build my standalone C++ file. I did also manually make a build by creating a build directory, running cmake .. and then make install, but the file structure that this generates doesn't seem to be correct. The hpp files it creates refer to each other in ways that g++ can't resolve, it almost seems like they want every subdirectory of pennylane to be directly specified in the include path. Am I missing something obvious here? And are there installation instructions/an example of a C++ file which uses the API directly somewhere? Thanks in advance!

[tomlqc]

Hi Jake,
That's right that we don't have much documentation about how to use the C++ API. To keep it simple, we can stay in the lightning repo and do the following.
You can find some inspiration in the CMakeLists.txt that we use for building the tests e.g. one can use lightning_qubit_algorithms to specify includes and libraries related to this project (you may need more than just this one). A draft example for a new source folder that includes main.cpp:

project(lightning_demo LANGUAGES CXX)
add_executable(lq_grover main.cpp)
target_include_directories(lq_grover PRIVATE ${CMAKE_CURRENT_SOURCE_DIR})
target_link_libraries(lq_grover lightning_qubit
                                lightning_qubit_algorithms
                                lightning_qubit_observables
                                )

You'll also have to add your source folder with add_subdirectory in the root CMakeLists.
To build, you can adapt the cmake commands in the test-cpp target in the Makefile and create a new target.
Does that help?

[tomlqc]

Hi @jzaia18,
Don't hesitate to ask any further questions 😃

[jzaia18]

Hi Thomas,

Thanks so much! Sorry on the late reply, I had a higher-than-average amount of workload due in the middle of the week. I'm planning on working on this tonight & tomorrow. I was able to get it to build my (basically blank) cpp file into an executable using the tip you gave me, but I haven't done much more past that. Thanks again!

[jzaia18]

Hi Thomas,

I think I've completed a (simplest possible/MVP) implementation of Grover's algorithm. I had a couple questions on how much you'd like it to be fleshed out:

• Are there any particular oracles you'd like to see tested, or can I just pick a handful?
• Is the expected-single-answer version of Grover's the one you're looking for, or would you like to see the version which does increasing iterations for oracles that may select multiple states?
• In my implementation I used the gate implementations from gates/cpu_kernels/GateImplementationsLM.hpp. Is this alright, or would you prefer I made my file adaptive to use the gate implementations for whatever hardware is being used during compile time? (If so I may need a nudge on where to look for how/where this is determined by cmake).

Thanks!

[tomlqc]

Hi @jzaia18,
It's good to share a simple MVP with us, so

• Feel free to choose an oracle.
• It's fine to have the single-answer version.
• Using GateImplementationsLM is fine too.

We may still have some questions afterwards on one of these points 🙂

[jzaia18]

@tomlqc I've started benchmarking against the python library and the python library is significantly faster, which tells me that it's probably making use of a better set of kernels for my system than the LM ones. I picked LM arbitrarily at the beginning since I was originally dev'ing in a VM and I wasn't sure what support it had for AVX512, etc. Looking into it further, it seems like LM is not going to be most performant on my system since it seems to be optimized for memory efficiency (and I'm sitting on 48GB of RAM). I suspect AVX512 should perform much better. Should I alter my C++ implementation to be more competitive, or are the performance of these benchmarks not something I should worry about at this time?

[maliasadi]

Hi @jzaia18 nice work so far! Yes, we generally expect significantly better performance when using AVX2/512+streaming kernels. We would be happy to review how you have benchmarked and compared these codes in your pull request, and we can continue the discussion there.

While it's optional, you can also disable the AVX kernels by rebuilding Lightning-Qubit with the ENABLE_GATE_DISPATCHER=OFF compilation flag (e.g., CMAKE_ARGS="-DENABLE_GATE_DISPATCHER=OFF" make python). Please feel free to reach out if you have any questions.

[jzaia18]

Even when compiling with ENABLE_GATE_DISPATCHER=OFF, the python version seemed to strongly outperform. I'm unsure if this worked as intended, maybe there's something weird going on in my python virtualenv. Either way, I added benchmarking information based on what I was able to collect thus far. Thanks for the help @maliasadi !

PR is marked ready for review @tomlqc, thanks again for the opportunity, and have a good day.