47 votes
Accepted

Can a Turing machine simulate a quantum computer?

Yes, a quantum computer could be simulated by a Turing machine, though this shouldn't be taken to imply that real-world quantum computers couldn't enjoy quantum advantage, i.e. a significant ...
user avatar
  • 1,457
28 votes
Accepted

Can a quantum computer simulate a normal computer?

Yes, it can do so in a rather trivial way: Use only reversible classical logical gates to simulate computations using boolean logic (for instance, using Toffoli gates to simulate NAND gates), use only ...
user avatar
16 votes

What are examples of Hamiltonian simulation problems that are BQP-complete?

There are plenty of different variants, particularly with regards to the conditions on the Hamiltonian. It's a bit of a game, for example, to try and find the simplest possible class of Hamiltonians ...
user avatar
  • 47.2k
15 votes

What would a very simple quantum program look like?

One way of writing quantum programs is with QISKit. This can be used to run the programs on IBM's devices. The QISKit website suggests the following code snippet to get you going, which is an ...
user avatar
14 votes
Accepted

Classical Memory enough to store states up to 40 qubits quantum system?

Suppose that you have a quantum algorithm with $2^{60}$ possible inputs. Suppose also that it would take 1 nanosecond to run this on a supercomputer (which is unrealistically optimistic!). The total ...
user avatar
14 votes
Accepted

Why doesn't the Gottesman-Knill theorem render quantum computing almost useless?

To my mind, this theorem is not very well stated in this form, if taken out of context. Where it says "phase gates", this may be misleading. It means specifically just $S=\sqrt{Z}$ and not what I ...
user avatar
  • 47.2k
13 votes
Accepted

How Mature is the Tensorflow Quantum Library

First we should take a step back. Is there any machine learning done a quantum computer that cannot be efficiently simulated on a classical computer? The answer currently (2020) is no. In this ...
user avatar
  • 505
12 votes

Can a Turing machine simulate a quantum computer?

To simulate the collapse of the wave function you'd need a source of randomness. So you'd need a probabilistic Turing machine.
user avatar
12 votes
Accepted

What would a very simple quantum program look like?

Assuming you are considering a gate-based quantum computer, the most easy way to produce an entagled state is to produce one of the Bell states. The following circuit shows the Bell state $\left| \Phi^...
user avatar
  • 492
11 votes

Hamiltonian simulation with complex coefficients

A conventional Hamiltonian is Hermitian. Hence, if it contains a non-Hermitian term, it must either also contain its Hermitian conjuagte as another term, or have 0 weight. In this particular case, ...
user avatar
  • 47.2k
11 votes

How would I implement the quantum oracle in Deutsch's algorithm?

There are two questions here. The first asks how you might actually implement this in code, and the second asks what's the point if you know which oracle you're passing in. ##Implementation Probably ...
user avatar
  • 3,908
10 votes
Accepted

Do real commercial quantum computers exist?

That depends on your definitions of "commercial" and of "quantum computer". The company D-Wave Systems has been offering what they call quantum computers commercially since 2011. Many things seem to ...
user avatar
  • 1,132
10 votes

Is the universe indistinguishable from a giant quantum computer?

I guess that he's right enough for the moment; quantum mechanics is part of our best theory of the universe, which by definition means that we think the universe works like that. It's pretty circular ...
user avatar
  • 1,457
10 votes
Accepted

How does one obtain amplitude information in Q#?

Yes, it is possible to obtain this information, but only for troubleshooting purposes, not for using it in the code. Dump functions dump the status of the target machine into a file or to the console ...
user avatar
10 votes
Accepted

Why can't a quantum computer strongly simulate itself?

Apart from the formal result about #P-hardness, there's something worth touching on, about the nature of strong simulation itself. I'll comment first on strong simulation, and then specifically on the ...
user avatar
10 votes
Accepted

Why are non-Clifford gates more complex than Clifford gates?

Yes, you are correct. Non-Clifford gates cannot be transversely implemented, instead implementation generally requires distilling magic states or Toffoli states. In practice this requires ...
user avatar
9 votes

Can a Turing machine simulate a quantum computer?

To complete what others have said: as far as we know a (classical) Turing machine cannot truly simulate quantum correlations. This is explicitly claimed in section Properties of the universal quantum ...
user avatar
  • 3,637
9 votes

How to compactly represent multiple qubit states?

$\newcommand{\ket}[1]{\left|#1\right>}$I'm not sure using sparsity is a good approach here: even single-qubit gates could easily turn a sparse state into a dense one. But you can use the ...
user avatar
  • 2,363
9 votes
Accepted

Obtaining gate $e^{-i\Delta t Z}$ from elementary gates

One way order to perform Z rotations by arbitrary angles is to approximate them with a sequence of Hadamard and T gates. If you need the approximation to have maximum error $\epsilon$, there are known ...
user avatar
  • 22.6k
9 votes
Accepted

Simulating Clifford + few-T circuits

Taking your comment to Kiro to its logical conclusion, the answer is 'yes'. The basic idea is to decompose the T gate 'magic' state $\tfrac{1}{\sqrt 2}\bigl(\lvert 0 \rangle + \mathrm{e}^{i \pi / ...
user avatar
9 votes
Accepted

Roughly speaking, How many qubits will be needed to study (or simulate) a molecule such as: C29H31N7O?

My quick answer: something between 4 and 4000. ^_^ The number of qubits in an electronic structure calculation depends on at least three things: Your basis set. Your qubit mapping. Your algorithm. ...
user avatar
  • 966
8 votes
Accepted

How to compactly represent multiple qubit states?

There are many possible ways to compactly represent a state, the usefulness of which strongly depend on the context. First of all, it is important to notice that it is not possible to have a ...
user avatar
  • 18.6k
8 votes
Accepted

Is there any source which tabulates quantum computing algorithms for simulating physical systems?

I believe what you're after is NIST's Quantum Zoo, a comprehensive catalog of quantum algorithms maintained by Stephen Jordan. Its sections include: Algebraic and Number Theoretic Algorithms (14 ...
user avatar
  • 1,679
8 votes

Is there any online Bloch sphere simulator?

This doesn't really answer the question as it's not an online simulator. It might still be relevant though as it is a way to produce this sort of gifs if one has access to the software. It is ...
user avatar
  • 18.6k
8 votes
Accepted

Is the SWAP gate a Clifford Gate? How would I express it using the Clifford Gate generators?

It's well known that you can make a swap out of three CNOTs. For reference, Stim's gate documentation includes H+S+CX decompositions of a lot of Clifford gates including the swap: ...
user avatar
  • 22.6k
7 votes

Is it possible to simulate a quantum computer in Virtual Reality? If yes, how?

Virtual reality in a classical computer is just a fancy front-end on top of a classical simulation. A classical computer can simulate all of the quantum physics happening inside a quantum computer, ...
user avatar
7 votes
Accepted

What are the preferred numerical methods to simulate the evolution of a state through a time-dependent Hamiltonian?

It depends on the Hamiltonian. There are three particular questions whose answers might influence your choice of strategy: Does the Hamiltonian have any particular structure or symmetry? How quickly ...
user avatar
  • 47.2k
7 votes

Are quantum simulators like Microsoft Q# actually using quantum mechanics in their chips?

Quantum simulators don't rely on quantum-mechanical effects in the physical chips; instead they simulate certain aspects of quantum state and operations on it using only classical compute. Universal ...
user avatar
7 votes
Accepted

Are quantum simulators like Microsoft Q# actually using quantum mechanics in their chips?

There is a distinction between what you use to write a program (the SDK), and what you use to run it (the backend). The SDK can be either a graphical interface, like the IBM Q Experience or the CAS-...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible