Example of a classically hard to compute kernel?

Are there any known kernel examples that are hard to compute classically but can be simulated using a gate model circuit?

Hi @ankit27kh!

There are kernels based on Shors algorithm or IQP algorithms. The former are not near-term, and the latter may not be very useful. The difficulty is to find quantum kernels that are hard classically, but still useful!

The kernels we use in PennyLane demos (here and here) are tiny and often reduce to a very simple Fourier series, so they are not a good candidate for classical hardness. However, they may be helpful for understanding quantum kernels.

Please let me know if this answers your question!

Yes, I was experimenting with different circuits. I wondered if there is an example of a classically hard kernel that has been successfully used for ML tasks with our current quantum computing capabilities.

Yes, this is definitely an active research area and I hope people can come up with these kinds of kernels soon!