Skip to main content
51 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 ...
Nat's user avatar
  • 1,497
29 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 ...
Sir Cornflakes's user avatar
19 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 ...
DaftWullie's user avatar
  • 59.3k
18 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 ...
DaftWullie's user avatar
  • 59.3k
16 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 ...
James Wootton's user avatar
14 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^...
dtell's user avatar
  • 512
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 ...
James Wootton's user avatar
13 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.
Bjørn Kjos-Hanssen's user avatar
13 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 the ...
ahelwer's user avatar
  • 4,138
13 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 ...
Jonathan Trousdale's user avatar
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 ...
dabacon's user avatar
  • 745
12 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, ...
DaftWullie's user avatar
  • 59.3k
11 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 ...
agaitaarino's user avatar
  • 3,827
11 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 ...
Niel de Beaudrap's user avatar
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 ...
blalasaadri's user avatar
  • 1,152
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 ...
Nat's user avatar
  • 1,497
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 ...
Mariia Mykhailova's user avatar
10 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 ...
glS's user avatar
  • 25.5k
10 votes
Accepted

How to selectively apply noise in Qiskit simulations?

Yes you can: When you build a noise model the noise is defined with respect to the name or label of gate objects, so you can use the labelto create multiple versions of a single gate but reference ...
cjwood's user avatar
  • 1,221
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 ...
M. Stern's user avatar
  • 2,457
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 / ...
Niel de Beaudrap's user avatar
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 ...
Craig Gidney's user avatar
  • 38.5k
9 votes
Accepted

Where does precisely the difficulty in exponentiating a Hamiltonian $H$ in the quantum simulation problem lay?

TL;DR: Hamiltonian simulation does not just mean "exponentiating $H$". It means finding a quantum circuit $U$ that approximates the matrix exponentiation $e^{-iHt}$. More importantly, the size of the ...
Sanchayan Dutta's user avatar
9 votes
Accepted

Are almost-Clifford circuits almost easy to simulate?

Short answer: Yes, this should be possible. However, the details have to be filled out. The key is to relate this to magic monotones. There has been some development since the 2016 Bravyi-Gosset paper....
Markus Heinrich's 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. ...
jecado's user avatar
  • 1,206
9 votes
Accepted

is cirq suitable for simulation of quantum error correction?

I wrote most (as in >50% not as in all) of the initial versions of cirq, and was its team lead for a couple years. I wouldn't recommend using Cirq as a tool for simulating QEC codes. Cirq is first ...
Craig Gidney's user avatar
  • 38.5k
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 depends on the context. First of all, it is important to notice that it is not possible to have a ...
glS's user avatar
  • 25.5k
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 ...
Andrew O's user avatar
  • 1,749
8 votes
Accepted

How to create an Ising coupling gate with Qiskit?

AHusain's answer is absolutely correct, but perhaps lacks some detail. The circuit that you want to implement is Basically, the key is to realise that you want to apply phase $e^{i\alpha}$ to the ...
DaftWullie's user avatar
  • 59.3k

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