5
$\begingroup$

Which kind of quantum circuits can be simulated with classical algorithms in a reasonable amount of time (for a large number of qubits)?

For example the ones with only Clifford gates. Or the ones with few non-local gates between the two halves of the circuit (via quasiprobability decomposition).

Are there any other examples of "constraints" that we can apply to a quantum circuit in order to be simulated faster than a standard classical simulation (i.e. it doesn't grow exponentially with the number of qubits)?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Can you edit your question to clarify what you mean by "standard simulation"? Given your examples I believe that you mean "simulated by a classical algorithm, running in time that grows polynomially with the number of qubits", but there's also some interesting questions about when we can fast-forward Hamiltonian simulation with a quantum computer. $\endgroup$
    – Mark Spinelli
    Commented Jan 24, 2023 at 18:16
  • $\begingroup$ If the gate set is classical, such as only CSWAP or CCNOT, then it’s efficiently simulatable classically, almost by definition. $\endgroup$
    – Mark Spinelli
    Commented Jan 25, 2023 at 3:16
  • $\begingroup$ @MarkS Edited! I hope it is more clear now. $\endgroup$
    – stopper
    Commented Jan 25, 2023 at 9:38
  • $\begingroup$ As far as I know, quantum circuits that have a tensor network (or matrix product state) representation can be efficiently simulated by a classical computer. $\endgroup$
    – Suriya
    Commented Jan 25, 2023 at 10:06

1 Answer 1

Reset to default
6
$\begingroup$

As mentioned, Clifford-gates circuits can be efficiently simulated but, in general, the most promising simulation methods are based on tensor networks. Through compact tensor representations and efficient operations, tensor network-based quantum simulation can scale to hundreds of qubits on a single GPU and thousands of qubits on multiple GPUs (today, the largest full statevector simulation can't go beyond 50 qubits even by using the most powerful supercomputer). Tensor networks work fine as soon as the level of entanglement in your quantum circuit is not too high.

For more details, take a look to TensorLy-Quantum, open-source Python library for tensor methods applied to quantum machine learning (GitHub repo).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you! Is there any important reference to study the theoretical limits of tensor networks? You mentioned that the level of entanglement has to be not too high, so I suppose that somehow the simulation time scales badly with the "amount of entanglement". Thank you again! $\endgroup$
    – stopper
    Commented Jan 25, 2023 at 14:12
  • $\begingroup$ Yes, that's exactly what I meant. However, as far as I know, there is no such a thing as a theoretical bound for the quantum circuit entanglement in tensor networks simulations. It's more like an empirical observation that derives from how tensor networks are built. $\endgroup$
    – SimoneGasperini
    Commented Jan 25, 2023 at 14:41
  • $\begingroup$ Ok thank you! Do you know any reference that can be useful to understand tensor networks? I have never used them $\endgroup$
    – stopper
    Commented Jan 25, 2023 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.