4 ms·

My question might be very stupid, but I am genuinely curious: I assumed a quantum computer is fundamentally different to a classical one and thus you needed ac

My question might be very stupid, but I am genuinely curious: I assumed a quantum computer is fundamentally different to a classical one and thus you needed actual quantum physics to build this kind of computer. So how can you simulate the quantum computer on a classical one?

detaro 10y ago
We can mathematically describe how a quantum computer works, so we can implement the mathematics in a classical computer. It's just slow (=higher complexity) in comparison. A quantum computer AFAIK can't solve any problems a normal computer couldn't solve, but it is a lot more efficient for some of them.
- jonknee 10y ago
  > A quantum computer AFAIK can't solve any problems a normal computer couldn't solve, but it is a lot more efficient for some of them. Technically correct, but some of the problems we want quantum computers to solve are currently infeasible by conventional means because of speed. Factorization for example, that's why public key encryption works (we can't brute force it), but a quantum computer could.
  - weinzierl 10y ago
    I didn't down vote you but here are a few remarks about your comment: >> [..] but it is a lot more efficient for some of them. > Technically correct Not quite. We know algorithms which have better time complexity on a quantum than any known classical algorithm that solves the same problem. Shor's algorithm is an example. We are not sure if a classical algorithm with the same time complexity exists. >Factorization for example, that's why public key encryption works (we can't brute force it), but a quantum computer could. Most (all?) modern public key algorithms are not based on the integer factorization problem.
    - cyphar 10y ago
      > >Factorization for example, that's why public key encryption works (we can't brute force it), but a quantum computer could. > Most (all?) modern public key algorithms are not based on the integer factorization problem. There are analogues for Shor's algorithm for the discrete logarithm and other similar problems.
      - PeCaN 10y ago
        Shor's algorithm covers discrete logarithm also. But most modern asymmetric algorithms are based on elliptic curves and other problems that quantum computers don't help with.
        serendipitous 10y ago
        The ECC algorithms used today rely on the "Elliptic Curve Discrete Logarithm Problem" and are very much vulnerable to (a version of) Shor's algorithm. Some would even say they are more vulnerable than RSA due to the much smaller key sizes (requiring less qubits).
brudgers 10y ago
My understanding is that the "magic" of a quantum computer is that it quickly finds a solution in a search space that grows exponentially based on the size of the input. Therefore it can be simulated by enumerating the search space and iterating over it. The simulation is based on describing the problem in terms of quantum computing and translating that description into a program executable by a Turing machine. The simulation allows testing the utility/correctness of programs for quantum computers.
gone35 10y ago
You can simulate a quantum circuit with a classical circuit, albeit with exponential slowdown.

detaro 10y ago

We can mathematically describe how a quantum computer works, so we can implement the mathematics in a classical computer. It's just slow (=higher complexity) in comparison. A quantum computer AFAIK can't solve any problems a normal computer couldn't solve, but it is a lot more efficient for some of them.

jonknee 10y ago
> A quantum computer AFAIK can't solve any problems a normal computer couldn't solve, but it is a lot more efficient for some of them. Technically correct, but some of the problems we want quantum computers to solve are currently infeasible by conventional means because of speed. Factorization for example, that's why public key encryption works (we can't brute force it), but a quantum computer could.
- weinzierl 10y ago
  I didn't down vote you but here are a few remarks about your comment: >> [..] but it is a lot more efficient for some of them. > Technically correct Not quite. We know algorithms which have better time complexity on a quantum than any known classical algorithm that solves the same problem. Shor's algorithm is an example. We are not sure if a classical algorithm with the same time complexity exists. >Factorization for example, that's why public key encryption works (we can't brute force it), but a quantum computer could. Most (all?) modern public key algorithms are not based on the integer factorization problem.
  - cyphar 10y ago
    > >Factorization for example, that's why public key encryption works (we can't brute force it), but a quantum computer could. > Most (all?) modern public key algorithms are not based on the integer factorization problem. There are analogues for Shor's algorithm for the discrete logarithm and other similar problems.
    - PeCaN 10y ago
      Shor's algorithm covers discrete logarithm also. But most modern asymmetric algorithms are based on elliptic curves and other problems that quantum computers don't help with.
      - serendipitous 10y ago
        The ECC algorithms used today rely on the "Elliptic Curve Discrete Logarithm Problem" and are very much vulnerable to (a version of) Shor's algorithm. Some would even say they are more vulnerable than RSA due to the much smaller key sizes (requiring less qubits).

brudgers 10y ago

My understanding is that the "magic" of a quantum computer is that it quickly finds a solution in a search space that grows exponentially based on the size of the input. Therefore it can be simulated by enumerating the search space and iterating over it. The simulation is based on describing the problem in terms of quantum computing and translating that description into a program executable by a Turing machine. The simulation allows testing the utility/correctness of programs for quantum computers.

gone35 10y ago

You can simulate a quantum circuit with a classical circuit, albeit with exponential slowdown.