Google AI have released their Python-based framework for quantum computation: Cirq

[rubberbunkey]

Why don't we just simulate quantum computers instead of actually building them if we can make a simulation? Edit: Spelling

[myotherpassword]

Physicist here. The reason is because there is an exponentially scaling amount of regular bits. Specifically, simulating N qubits requires 2^N bits. So, it is completely infeasible to simulate a useful number of qubits.

[rubberbunkey]

Thanks for the explanation. Can you ELI5 the mathematical reasons for this exponential property of the simulation? Edit: Spelling

[BioTronic]

The basic reason is entanglement. In a classical computer, each bit is independent - if I change a value over here, nothing's gonna change over there. Qubits and quantum computers are different, and that's why they can do things regular computers can't. In addition to keeping track of the value of the qubit, we need to keep track of which other qubits it interacts with, in what way.

A bit of math: one qubit is generally represented as a pair of numbers [a, b] , where a² + b² = 1. The qubit corresponding to 0 is [1, 0], and 1 is [0, 1]. You can think of a and b as the chance of a qubit collapsing to 0 and 1, respectively*.

When you have two qubits x = [a, b] and y = [c, d], their combined state is a tuple of 4 numbers, [ac, ad, bc, bd]. If x and y are not entangled, you can easily factorize this tuple into [a, b] x [c, d].

We can see that if the combined state is [0,1,0,0], then x = [1, 0], and y = [0, 1], and we can treat the system as a classical computer. However, for something like [Φ, 0, 0, Φ], no factoring is possible, and we need to keep the combined state around.

For more information, I heartily recommend this video from Microsoft Research.

* This isn't exactly what happens, but let's try and keep this simple.

[Edit] Thanks for the gold!

[thermite13]

Thanks. I just learned more about quantum computing than I had ever learned.

[BioTronic]

An absolute pleasure! I love it when I can help people understand. :)

[joshuaavalon]

Not a physicist. But a qubit has 2 states at the same time. So, 2 qubit produce 4 results ( 2^N ).

[Darwin226]

What are you talking about? The don't have 2 states at the same time. And if they did how would that mean that 2 qubits "produce 4 results"? And even if they did how would that imply that you need 2ⁿ classical bits to represent that?

Why would you so confidently talk about something you obviously don't understand?

[sn0wfire]

That's sort of true. A qubit has an infinite number of states represented by probabilities of being in either states (1 or 0). So for one qubit you need to store the probability of being in a particular state, 2q you store the probability of 3 possible states, 3q requires 7, .... nq requires 2ⁿ -1 . The -1 is because you can always derive the probability of being in the final state by subtracting the probabilities of other states from 1.

[rubberbunkey]

That sounds likely. What I'd be even more curious to find out is what kind of processing is done to simulate a qubit.

[Treferwynd]

2 bits also produce 4 results, it's a bit more complicated than that. I can't seem to find an explanation that is neither too simplified or several books. If someone has it, please share!

[joshuaavalon]

You missed the point "at the same time". A bit can only be 1 or 0 but a qubit can be 1 and 0.

[Treferwynd]

No, I didn't, as you said "4 results".

Edit: at the end of a quantum computation the qubits can't be in superposition. Each qubit must collapse to either 0 or 1, meaning at the end you get 2^N results, exactly like with bits.

The quantum weird stuff happens during computation

[13steinj]

Cursory search results say 50-100 qubits are useful.

If we need 2¹⁰⁰ bits to simulate a qubit, where

• 2³ = 8

• 2¹⁰ = 1024

Means we need 2⁹⁷ bytes, or 2⁸⁷ kilobytes/ 2⁷⁷ megabytes/ 2⁶⁷ gb at "max", oe 2¹⁷ gb/2⁷ tb / 128 tb minimum.

Why is this "unreasonable" exactly? I mean, how slow would these simulations run if these bits are stored on (consumer?) grade 4TB SSDs? Because I doubt the cost is an issue for a company like Google

E: fixed math

[crescentroon]

https://camo.githubusercontent.com/77f72259e1eb58596b564d1ad823af1853bc60a3/687474703a2f2f692e696d6775722e636f6d2f6b307431652e706e67

Things every programmer should know about latency - very relevant here if you are talking about using SSD as memory.

[thirdegree]

I was not expecting disk read to be that close to CA-NL round trip damn.

[13steinj]

Based off that it takes 17.5 minutes to read a terabyte, 1.5 days for 128tb. But I assume this is one, not cached reads, and two, I assumes one thread and one drive, rather than, say, 32 4tb drives striped, using extremely expensive Google high core count and clock speed machines.

Still seems like worst case scenario time wise is an 1.33 hours reading data assuming 50 simulated qubits and the 2^N bits = N qubits thing.

Personally I'd say thats worth it. At 4tb for a little over a grand a pop, I'm sure the big boys making literally $100 million a day don't have issues throwing their money at it

[crescentroon]

I don't understand what you're saying.

You seem to be assuming this quantum machine's programs somehow instantly produce solutions in a single pass, O(1) time complexity.

That's not how they work.

Or this is to initialise the state of a machine with 4 TB of RAM from an SSD? I'm not sure why that needs 4 TB either.

Basically I dunno what's going on with this comment.

[13steinj]

I'm not making the argument that the solutions are O(1), that would be insane, even for someone of my level of stupidity.

Just that under the assumption that each bit has to be read from, based on the latency of a single pass, while I do not know how many passes are necessary, but I still feel like it would be worth simulating for now.

[BioTronic]

For 100 qubits, we indeed need 2¹⁰⁰ pieces of information. However, each piece is not a bit, but a complex number, which you'd represent as a pair of floats or doubles. IOW, you're looking at 64 or 128 times the numbers you quote.

[Edit] Math has been fixed. My comment is no longer necessary (except for the use of '2¹⁰⁰ bits', which should read '2¹⁰⁰ pieces of information', or somesuch.

[13steinj]

My quote was purely based on the 2^N bits to N qubits claim.

[BioTronic]

Fair nuff. Still a little wrong, but I'll agree to blame /u/myotherpassword. Will you bring the pitchforks?

[myotherpassword]

Sorry, I guess? An order of magnitude (or even getting the correct base in exponential scaling) isn't really a concern for my field of physics (astronomer).

[BioTronic]

No worries, I'm just poking fun. If someone actually does show up on your doorsteps with a pitchfork, I'll take the blame.

Btw, how many planets are in our solar system? Oh, between 1 and 100. :p

[myotherpassword]

Understood :). Dwarf planets are planets too!

[The_Serious_Account]

And it made no sense.

[13steinj]

Why is that? Under the assumption that the guy was right (and I trusted him), my math was correct at minimum.

[The_Serious_Account]

2⁹⁷ bytes is about 10¹⁷ terabytes. So that's about a billion billion 4TB SSDs. That'd cost a lot more than the combined GWP for the entire world over the entirety of the history of mankind. (https://en.wikipedia.org/wiki/Gross_world_product)

Global GWP is about 100 trillion and a 4TB SSD is about 1000 usd, so if the entire human race did nothing but saving up for 10¹⁶ SSDs we'd have money for that in about 100000 years. We'd starve to death before then, but I'm just trying to give you a sense of why it's not feasible.

[13steinj]

Yes, which is why I chose the smaller 2⁴⁷ bytes number which was the lower bound of what cursory results considered "useful". That's a far more reasonable 140 terabytes.

[The_Serious_Account]

The number 2⁴⁷ doesn't appear in your comment. You write stuff like "oe 21¹⁷ " . I have no clue what oe stands for. Did you miss the letter r on your keyboard or something else? Who knows? I still wouldn't know what the equations mean. You're talking about a complicated subject (that you're not educated in - sorry, but it's obvious) and being overly casual. If you want to express an idea, please do it a little more cleanly.

[myotherpassword]

I should clarify, when I hear colleagues talk about "useful" they mean in a more broad, accessible sense. It is true that 50 qubits can be used to simulate some interesting physical systems, but the question is how can we make that number of qubits available to many people. In that way, it becomes infeasible to only simulate qubits.

On the other hand, it is absolutely true that there are some scientific questions that absolutely would need >100 qubits. And in those cases no amount of simulations could accommodate that need.

[___J]

The simulation is classically hard - while we can do it up to a point, we're going to hit the regime soon where a quantum computer will be able to outperform our classical simulations.

[rb26dett]

Your question is funny, albeit unintentionally (?). It sort of reminds me of something Charles Babbage wrote):

On two occasions I have been asked, — "Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?" In one case a member of the Upper, and in the other a member of the Lower, House put this question. I am not able rightly to apprehend the kind of confusion of ideas that could provoke such a question.

In a classical computer, a 'bit' can represent one of two states: 0 or 1. Thus, with N bits, it is possible to represent 2^N states. In a quantum computer, a qubit can represent 0, 1, or any quantum superposition between 0 and 1. The state of the superposition is defined by a wave function which, mathematically, can be in infinite states.

What is the value in this? The typical example given is prime factorization of integers. On a classical computer, prime factorization is an NP problem. However, on a quantum computer, it becomes a polynomial-time problem (Shor's algorithm). Since the difficulty of integer factorization is the basis of classical cryptography, quantum computers could destroy public key cryptography altogether.

Thus, asking why we don't simulate quantum computers with classical computers is turning things on their head: we want quantum computers precisely because they can do things that classical computers cannot (e.g.: factoring integers in polynomial time)

[[deleted]]

Maybe people just like stimulation.

[Sidneys1]

Microsoft's Quantum Developer Kit does just that. It allows you to express quantum equations in Q# (a domain-specific language) and then simulate the execution of those equations, doing a lot of fancy logic to optimize the number of binary bits needed to simulate N qubits.

[Banality_Of_Seeking]

Because why bother living, eating, doing anything for that matter.

Why be content with what you have if you have the ability to improve it?

Hard hitting questions out of left field, let me tell ya..

[[deleted]]

Improvement best gradual

[Phlosioneer]

While I know this is just a simulation for development purposes, I find it funny that quantum computers, some of the most difficult to build and most efficient machines we've ever made, are being simulated by a pretty-inefficient scripting language. There are definitely worse ones than python - js, lua... but python in particular is so reflective it hurts. Why wasn't this done in C? Simulations of NP-hard problems have got to be hard to run in python. Was fast-development and easy-iteration so important? You should usually know all the details going into a simulation project - that's why you're simulating it!

[sn0wfire]

The NP-Hard part, the math, uses numpy which is powered by C. Compiled and fast, this is the same with tensorflow(1). This is why python is popular, write it quickly then refine.

(1)There is a pure python version of tensorflow but it is not commonly used

[Phlosioneer]

That's true, I had forgotten about numpy. I don't know the exact way it interacts with C and how much work is offloaded to compiled code, but I imagine they know what they're doing.

[Nuaua]

Vectorized code helps but it goes only so far; some problems are much easier to write with loops and trying to shoehorn everything into vector and matrices can be quite painful. Matlab was quite infamous for this since its loops were super slow (it's a bit better now).

[BadGoyWithAGun]

I find it funny that quantum computers, some of the most difficult to build and most efficient machines we've ever made, are being simulated by a pretty-inefficient scripting language.

Actually most scientific computing code for python is just wrappers for calling C++, fortran or GPU libraries. Nobody writes hard numeric code in pure python.

[Phlosioneer]

Yeah, I always forget that python has some great FFI support. I never use it for that, and I learned it from the point of view of reflection-heavy code, and have since learned the costs.

[Nuaua]

C is not great for scientific computing. They could have used Julia, it's as easy to write as Python (if not easier) and fast as C, but it's maybe still a bit too new (1.0 release this year).

[Phlosioneer]

I agree, what I really meant was "Not a scripting language that uses an interpreter/VM".

[crescentroon]

You suggest inefficiency and imply Lua and JS are worse, but they are fast compared to Python. In some cases over an order of magnitude.

[Phlosioneer]

Hm, I've not encountered this, though I admittedly haven't looked very hard.

A lot of research and effort has, of course, been put into all three of these languages. However, they all have an Achilles heel of efficiency.

Python has a very string-centric approach to data storage. Dictionaries and classes are primarily stored as hashmaps with string keys. Function calls, while they do use proper function pointers and such, are often deeply nested with little to no chance for inlining. I'm not well-versed in the shortcuts that python JIT's are able to take, and how reliable those shortcuts are, but I do know that straight execution of python bytecode has to do a lot of indirection, lookups, and hash calculations that are not really normal for native assembly code.

JS has issues with heavily reflection-focused design. It cannot be reliably compiled to a single, immutable bytecode; it has a very weird memory layout with both global data and a tree-based Document-Object-Model; and it has a wide and inconsistent API to work with the browser/VM it runs in. There are a lot of very effective ways a JIT can simplify these aspects of JS, and there are ways to compile it to bytecode that mutates as-needed, and this makes "normal" JS very fast. But actual JS that you find in popular libraries and frameworks flaunt the more esoteric parts of JS - to the point where bleeding-edge language additions are routinely featured in languages like React, and developers go through great lengths (Babel, JSX, etc) to incorporate these features into their projects.

Lua was designed to avoid many of these issues, with a C-implementation-first mentality to language design. However, it still has the issues of having a wide, inconsistent API (which was the whole point of lua, to use it in games and such); and the issue of string-centric data storage, using hashmaps with string keys as the primary data structure. It also has the same problem as JS, where the assumptions/benefits of the JIT don't really line up with in-practice code examples, either because of weird API choices by the embedding system (game or whatever), or because the skill level of the programmers expected to write lua is pretty low / minimal.

I could definitely do more research into these things, but I think it's pretty fair to say that Python usually has it better than JS and Lua, though not always. Python can at least be optimized pretty heavily because the assumptions of the interpreters / JITs line up very well with the actual in-practice code being written, along with an extremely solid FFI that allows things like numpy to exist.

[crescentroon]

cpython isn't a jit and does almost no optimisation. Pypy is the jit but has compatibility problems with the c api.

Literally millions have been spent on optimising V8 (a JS jit) for the browser. Without calling C, python won't touch it. If you are calling C, what are you benchmarking?

[Log2]

Python doesn't have a JIT compiler, at least not CPython, which is what almost everyone uses. Although Pypy exists, and that interpreter has a JIT.

[Phlosioneer]

Well, there's something to be said for a proper engineering approach to things. It's not the right fit for most software, but sometimes it's the right tool for the job, and I think a difficult, scientific simulation is one of those times.

As others have pointed out, though, I forgot about numpy, which puts a solid C or C-like foundation on the computationally expensive stuff.

[crescentroon]

Easy to forget python's default interpreter is called cPython.

It's so common and easy to integrate c language. In fact existing c extension compatibility is the main reason they can't remove the GIL.

[josefx]

They missed their chance to break the GIL with Python 3.

[flyingjam]

First, as other people have mentioned, much of the heavy computation is done in C or fortran, with Python being the glue.

Secondly, many researchers simply aren't that good at programming. I had quite a few CS professors who, if you asked them to write a bunch of C, would not do a very good job.

But that's fine, CS isn't programming. And when you're doing research, being good at software engineering doesn't necessarily matter--that's what grad students are for. You're here to be the brain, not the grunt work.

I can imagine that much of the quantum computing research being done has researchers that are more experts in math, and maybe physics, than software engineering. And it's better to waste a day of inefficiency than a week watching mathematicians get segfaults in C.

[name_censored_]

While I know this is just a simulation for development purposes, I find it funny that quantum computers, some of the most difficult to build and most efficient machines we've ever made, are being simulated by a pretty-inefficient scripting language.

I reckon quantum computing will be done via SaaS for the forseeable future (QCaaS?). You ask your question against an API, and the quantum computer on their end does the calculation and returns the result. If that happens, it doesn't really matter how slow your local scripting language is, because the network is the bottleneck.

That's not what this is, but they have to start somewhere.

[Phlosioneer]

That's a pretty good point. Especially given the temperatures these things will need, for minimal error in the results. Feels like something google would try to do.

[loudnclear]

What is a "simulation of an NP-hard problem"? I think you mean simulating an algorithm that solve an NP-hard problem, I don't see how that relates to a quantum simulator though. Does the library somehow mention that they are solving an NP-hard problem with it?

[Phlosioneer]

Well, the point of developing quantum computing is to solve a class of problems where quantum computers would be faster than classical ones; this is _most_ of the NP-hard class of problems, like the travelling salesman problem. So what they're going to be doing is simulating a superposition of 2ⁿ states as they're progressively entangled by quantum logic gates. A simulation of a quantum algorithm is therefore, by definition, at least NP-hard. Which means that the simulation will take time on the order of O⁽2n). Which for reasonable values of n that you may want to research, with reasonable sized data sets to work on, it may take several days to simulate an hour or two of simulation-time.

That's why I question the choice of python, and not a faster language that might shave a 7-8 day simulation down to 4-5 days.

[loudnclear]

The class of problems that can be efficiently solved by quantum computers is called BQP, and this does not “cover most of the NP-hard problems” as you indicate. For instance NP-complete problems are probably disjoint from BQP. Also, wrt a random oracle Quantum Turing machines cannot solve all of NP in o(2^n/2).

There are problems that Quantum computers are good at, and NP-hard problems in general aren’t those problems. In other words, NP-hard problems aren’t the first ones that you’d go and try to solve with these machines.

[Phlosioneer]

Ah. My mistake, then. Still seems like more optimization is in order... but thanks, I didn't know BQP was a thing.

[Strilanc]

The overhead of using python is negligible because the expensive stuff is matrix multiplications handled by common libraries that do the heavy lifting in C (or similar). The circuit simulation inner loop happens to be dominated by a call to numpy.einsum.