I don't think that's what most people familiar with the topic believe. It's just considered to be very hard (and some think it's so hard that it may be practically impossible for a very long time).
Somebody finding that quantum computers can solve NP-hard problems would be very suspicious. Other than that it would need someone to find a flaw with quantum mechanics.
It was to my understanding that some NP-complete problems - like factorization - are (theoretically) solvable in P time using quantum computing, all within (and indeed as a result of) the constraints of quantum mechanics, perhaps utilizing Shor's algorithm. And that this fact does not imply P=NP, but rather that we'd have a computer that could perform some exponential functions as if some logarithm were applied to them.
I'm no expert, but at the very least I believe it's recognized that some subset of NP problems, perhaps not NP-hard, should be solvable as if they were polynomial, using quantum computers.
That said, my knowledge of this subject starts and ends with things I've read on the internet, so I could be mistaken. Either way, this[1] was a very interesting introduction to some of the implications/concepts that are involved with this.
Factorisation is very, very, very unlikely to be NP-complete.
P is a separate class from the class of problems considered efficiently solvable; BQP is the class of problems that are efficiently solved by quantum computers, and it is believed that BQP is strictly larger than P.
I have also heard that it is not a true Quantum computer although it solves the ising problem faster than simulated annealING systems and it also uses qBits (>1024 atm) and I believe both Google and UCLA own or at least use Dwave systems. So if it looks like a duck and quacks like a duck.... Anyways nice article even if it did not mention Dwave. The Hacker News community comments section can take care of that!!
They really aren't all that similar, and it only solves a tiny subset of Ising problems (which match D-Wave topology), and they really aren't faster than a single modern Intel core running a reasonable algorithm.
It can not factorize numbers in polynomial time, it can not speed-up chemical simulations, it can do basically nothing that a quantum computer does, besides simulating itself. It's also not obvious in any way what use there is in simulating quantum annealing.
If you mean the D-wave devices specifically, the kerfuffle is that the low-clockrate quantum device does not complete tasks any faster or cheaper than a comparably priced classical computer, and the open question as to whether they can ever be made to operate faster. That's why there's only research labs buying them. But the device does work.
I'm not an expert in the field, but I do annealing work on occasion (simulated annealing, which is kind of like copying polymer annealing).
Simulated annealing is just an optimization. I use it for modelling human motion. You have the position and acceleration of each bone in the legs and feet. You start by deciding on a variable (say, reducing energy expenditure for gait), and then letting the algorithm alter variables and attempt to minimize a variable.
So if quantum annealing is anything like simulated annealing, you aren't "solving" for a single, correct answer, but getting a solution that minimizes or maximizes an outcome faster than brute force.
So a quantum computer could solve "What is the factorization of this huge number?", while quantum annealing could solve "Given these 30 different engine configurations, which combination of intake pressure, fuel flow rate, turbocharger performance curve, and engine timing would result in the best fuel efficiency?"
The advantage of a quantum annealer is in cases where there is a large, narrow spike in the way of moving to a good solution. The quantum optimizer has a chance of "tunneling" through the spike to find a better solution. A classical version of simulated annealing would have to "climb" over the spike, or more likely just be stuck on the wrong side.
Optimisation and Search problems are not fundamentally different; one can usually translate a problem from one world to another. For instance, take your optimisation problem and rephrase it as:
Here's a value of the fuel efficiency; find me a setting of the parameters that achieves a fuel efficiency better than that.
It's now a search problem. To find the best fuel efficiency, just binary search over possible values of the efficiency.
Where D-Wave differs is that you can only solve a particular kind of optimisation problem, and this kind of problem can't encode general computation. General quantum computers can solve general computation problems, not just the simulated annealing of D-Wave QC.
D-Wave isn't trying to build a general purpose quantum computer. As it stands, they've been trying to optimize a computer that executes a particular algorithm (and as it stands, it's not faster than optimized classical algorithms). It is an open research question if D-Wave's architecture actually utilizes any quantum effects to give it an advantage over classical architectures. D-Wave hopes that there will be enough problems that their machine is good at that their approach will be justified.
D-Wave markets themselves as having hundreds or thousands of qubits, but these qubits aren't easily controllable or measurable in ways that would allow Shor's to be executed on them (for example), so at the least, it seems like dishonest marketing. In order to build a general quantum computer, you need to be able to apply gates to arbitrary collections of qubits.
I'd recommend everyone to check out IBM's online http://www.research.ibm.com/quantum/ for a brief tutorial on how you need to be able to wire qubits together, and what a general quantum computer would look like. (You can even execute the result on an actual Quantum Computer; so it gives some idea of what an API would look like).
This is the first research paper they've published; they do not have a strong research presence precisely because they did not allow publication of research carried out at Apple, making it difficult to hire researchers whose career depends on said publications.
Furthermore, AI is very different from the fundamental research underlying quantum computing.
Yes. But GP was simply refuting the assertion that all Apple does is "Plug computer parts together, wrap in a shiny case, add software," not claiming that Apple has a strong research presence or is working on a quantum computer.
"Quantum computing has long seemed like one of those technologies that are 20 years away, and always will be."
I've just completed a PhD in this area, and I've never heard this sentiment before. It seems quite unlike fusion research, which is famously always 50 years (?) away. Quantum computing research is proceeding at a rapid pace, and actually it is perhaps only 20 years old in total. Although Feynman considered something akin to a quantum computer in the 80's, it really wasn't until the 90's that quantum error correction became a thing. So it really is a very young field of research. The "old-timers", they are all about 40 years old now, unlike other areas of physics where the oldies really are very old!
I've just completed my PhD as well. My research was all computational and consisted mainly of molecular dynamics simulations and machine learning. However, I did a lot of quantum chemistry work (QMC, DFT) as well and have taken QM classes — quantum mechanics, quantum field theory, density functional theory. Any other knowledge that would be relevant for quantum computing I've learned on my own (Nielsen and Chuang, etc.)
I'd really like to work for one of the quantum computing companies (Rigetti, etc.) or research groups (QuAIL), but I'm not really sure how to proceed in applying to these places given that my background isn't exactly quantum computing research. Since you have experience in this area, would you have any tips on how to apply to one of these groups? My current line of thought is to just apply directly via their websites, and if I don't hear anything back, begin contributing to the relevant Github quantum computing projects as proof of capability. Would you have any suggestions for a better approach?
Hi Xcelerate, Will Zeng from Rigetti Computing here. While you're right that it is a bit of a move, backgrounds in computational chemistry are very interesting to us as quantum simulation, especially electronic structure, is a big application area for near term QC.
If you or anyone else with similar background is looking to get into quantum computing, then send along your resume at will@rigetti.com
In my experience, this view is very prevalent, especially in physics departments. Once you hit the job market it is one of the questions you'll have to answer during interviews, so be prepared! I do agree that there is steady progress, which definitely has helped the field. Context: worked in quantum computing for 10+ years (and was a prof).
I was not aware of Rob Schoelkopf's initiative so far (http://quantumcircuits.com/), I think this could be serious competition for John Martinis & Google.
From their website it seems that they use a 3D cavity approach to quantum computing, which is (or at least was) pursued by IBM as well. Here, instead of using superconducting resonators on a chip, you use superconducting 3-dimensional cavity resonators (typically made from Aluminium) in which you place "naked" qubits that are fabricated on a Sapphire substrate. The advantage of this is that the attainable quality factor of the cavity is much higher than for a coplanar waveguide resonator (although those resonators have caught up quite a bit thanks to work that was done e.g. by the Martinis lab), and that there are fewer noise sources around the qubits.
Personally my current bet would be on Martinis or Schoelkopf to win the race, as they have the best access to both funding (though I don't know the funding details of QuantumCircuits) and Academic resources. Most of the original work on Transmon-based qubits was done at the Schoelkopf lab, and it seems that he has excellent technicians on his team.
In general though it still seems more probable that a ion-based quantum computer will be the first "real" quantum computer, as the technology is more mature and (for small numbers of qubits at least) easier to scale.
I wonder if anyone is pursuing Andrea Morello [1] and his team's silicon-based quantum chip idea, which they've also said has much better stability than superconducting qubits:
I'd much rather ultimately see silicon-based quantum computers, which may eventually become advanced (streamlined) enough to be used by mainstream users, too. Quantum computers using superconductors and liquid nitrogen will never become mainstream. They would just be used by corporations and governments.
So I hope there will be more investing in silicon-based quantum computing research sooner rather than later. Or if not silicon, at least another material that could one day become as cheap and practical.
EDIT: As for who will be the "first" with a practical quantum computer, it does seem like Google will be the one to release a 50-qubit computer this year or the next [2]. There are like 10 other companies that have built 5-qubit quantum computers, but that was still mainly a science experiment to prove that a quantum computer can be made at all.
A 50-qubit quantum computer would establish a new threshold and according to Martinis [3], at least, it should be easier to scale from that point forward. In other words, the "quantum era" may actually begin then. I imagine those "stuck" at 5-qubits still have a long way to go before they can scale quickly beyond that.
Is his machine adiabatic? Because calling it D-Wave 2, and only talking about "quantum supremacy" instead of the well defined "adiabatic" make it too suspicious.
Andrea Morello's devices are essentially quantum dots - isolated electrons that behave like they are bound to a single atom. Unfortunately, almost all quantum dots require dilution refrigerators. These things are past liquid nitrogen and even liquid helium - they use interesting phase change properties of a mix of helium-3 and helium-4 to lower the temperature to hundreds of millikelvin.
Really the only game in town currently for room-temperature quantum computing are impurity centers in diamond (most commonly nitrogen-vacancy centers). Unfortunately, there are still many difficulties there, especially since nanofabrication of diamond and precise implantation of the impurities is still a new field.
My understanding (which is limited!) is that there are some apparently NP-complete problems that are P for a quantum process.
Now, it may be that these problems were never actually NP-complete, but are a superset of P for quantum computers.
Or it may be that quantum computers can really solve some NP-complete problems in P time.
Either way though, it isn't a consequence of CPU-cycles per se, but the underlying mathematical distinction (ie, what a silicon vs quantum computer does, not what it can do in a "cycle").
If quantum computers could solve NP-complete problems efficiently, the entire community would astounded.
As it stands, quantum computers can solve some problems faster than classical computers currently can; factorisation, discrete log and other problems with a particular kind of repeated structure are some such problems. However, we do not know for certain that these problems are not efficiently solvable using classical computers (I'd bet that factorisation will be put in P within my lifetime).
A big goal of the QC community is to demonstrate quantum supremacy: to unconditionally show that quantum computers can solve a problem with fewer resources than classical computers. We've made progress on this (check out Scott Aaronson's blog for more info), but still haven't achieved it.
Lastly, a small nitpick. "P time" is not a meaningful phrase; P is a complexity class consisting of problems solvable efficiently (i.e., in polynomial time) on classical computers.
The class of efficiently solvable problems on quantum computers is BQP: Bounded-error Quantum Polynomial-time, which means that BQP is the class of problems that are efficiently solved by a quantum computer, but only with some probability bounded away from 1/2. This means the QC can return incorrect answers, but there are techniques to reduce the error probability to extremely small values.
The classical analogue of this class is BPP, which is Bounded-error probabilistic poly-time. There's a conjecture that BPP=P, and if we have any sort of crypto then the conjecture is true.
> there are some apparently NP-complete problems that are P for a quantum process
The definition of P refers to deterministic machines; no quantum. 'P for a quantum process' is a meaningless phrase. Problems solvable in polynomial time by quantum computers are contained in the classes EQP (if the answers are to be always correct) and BQP (if the answers are to be correct with a probability which may be made as high as desired).
> it may be that these problems were never actually NP-complete, but are a superset of P for quantum computers.
'NP-complete' is not an exact synonym of informal concepts like 'hard' or 'intractable'. It has a precise definition: NP-complete problems are those for which are simultaneously NP (the solution can be verified in polynomial time) and NP-hard (every instance of any NP problem can be reduced in polynomial time to it). There are problems that have been proved NP-complete. For others there are no known polynomial time algorithms, but they are suspected not to be NP-complete either. If P = NP, the notion of NP-completeness becomes trivial and equivalent to simply being in P. There's no way a problem now known to be NP-complete will later be shown not to be.
> Or it may be that quantum computers can really solve some NP-complete problems in P time.
This has not been proved false, but generally considered unlikely. (Also, 'some NP-complete problems' would imply 'all of them', by the definition of NP-completeness.)
Apart from speed the only other thing is memory. And yes, for example simulating a quantum system takes exponentially much classical memory (just to store the state of the system). This is one of the proposed killer apps for quantum computing.
It's not a question of possibility, but rather speedup. The three "flagship" algos are for unstructured search[1] (not clear if really useful), factoring[2] (useful to crack public key crypto), and more recently there is a result that shows that random instances of general linear problems can be solved faster[3].
Another class of algorithms use quantum computers as simulators (e.g. for chemical simulations). You can also encode certain optimization problems as "constraints" in a quantum system and hope that quantum dynamics will find good solutions to the optim. problem faster.
Grover's algorithm is also (theoretically) used for breaking symmetric crypto, by halving the exponent needed in brute force search. It's the main reason to move from 128-bit ciphers to 256 bit.
Yeah it really is. Quantum states just do not even fit in classical memory. Like, exponentially so. The parent was specifically asking about "possibility" not speedup.
That's just a matter of speed no? It's not an impossibility result like Turing's; classical computers can compute whatever quantum computers can. That's the Church-Turing hypothesis.
It's just a matter of speed, but there's no need to invoke the Church-Turing hypothesis.
One of the first things proven[1] about BQP is that it's contained in P^#P, which is contained in PSPACE. That means a Turing machine can simulate any quantum computer with only polynomial space (but possibly very slowly).
I am not involved in quantum computing at all, and only have read a few articles, but my understanding is:
Calling it a speed up is kinda correct but seems slightly wrong to me. It is a completely different computing model which tends to use different algorithms that make solutions to certain problems feasible on a quantum computer that aren't on an equally powered classical computer. That is why it's so powerful, but at the same time, classical computing could stay "faster" than quantum computing for a long time, or even forever.
IANAPhysicist, but the analogy I use for my relatives is that electronic->quantum is similar to the jump from clock-work->electronic.
Most concepts carry over, but some just don't make sense anymore, and a lot of effort must be invested into fundamentally new click-clack (or zip-zap) arrangements to get things done. A large part of the "intelligence" in the final system is actually latent in its structure.
Anyone interested in learning quantum mechanics should first learn/review their linear algebra. Understanding quantum states and quantum measurements is really not that complicated once you're comfortable with vectors and matrices.
That's so boring! I recommend people learn whatever they want, and then if needed go and read a maths book. Much more fun that way. (Btw, I don't mean to dis your book, it looks good to me.)
Edit: just to elaborate on this. I hear often from people "what math do i need to learn so i can do X?" And I just think that alot of the time people should just do X and this will force them to figure out the math as needed. Learning math from a book is brutally difficult! Just like learning a programming language, what is the best way to do that? You start with a project that you want to do. People who want to read the "pre-requisite book" often-times just seem to be deferring the real crunch that happens when you actually get down to the business of actually learning X.
I can understand your approach. It helps to learn a topic (like linear algebra) when you can immediately see it's applications. However, I'm not sure it would work here; for one, quantum mechanics is not an "easily" understood application, like, say PCA, or DFT, or other such things.
I'm reminded of the film "October Sky" where Jake Gyllenhaal's character (and I feel like a terrible nerd for not recalling the character, who is (was?) an actual NASA engineer, iirc), upon witnessing Sputnik-1 on a clear night, became obsessed with space flight and rocketry in particular. Got himself a bunch of really advanced texts on the subject and just powered through them, lazily learning the necessary math as needed, as you suggest. Once a poor student (bit of a slacker), he went on to make himself some rockets in relatively short order.
Excellent flick. If you haven't seen it, I recommend giving it a watch.
Not yet, but I'll be happy to get a wallet going to make this happen. Any recommendation for a good bitcoin wallet provider? I don't care about mobile app: web-only is good enough for me. Ideally fully offline.
My PhD is in biophysics. The Hamiltonion is a functional, pretty much all QM is application of Hamiltonians. I know both LA and FA; LA is basically introduction to FA.
It really depends on the area. For quantum computing and quantum info theory it seems that mostly it is just linear algebra. The functional stuff is left for the really really clever people only (not me btw!)
The way you describe it sounds analogous to computers: like saying "you only need to know C, not transistor physics, to program a computer". You can code on an existing machine, port your code to a new machine, but you'll never invent a new machine or architecture.
Your question is rather tautological... You can pick a text book or even an online tutorial.
Understanding diagonalization (and more generally, spectral theory), scalar products, and norms would be a great start. Then you can pick any quantum information textbook.
I think most would say that functional analysis is a generalization of linear algebra and that you absolutely need your linear algebra first. (Functional analysis is often thought of as infinite dimensional linear algebra.) Moreover, (finite dimensional) linear algebra is sufficient for learning theoretical quantum computing where there is a finite number of states.
It was a collaboration with Scott Aaronson ( http://scottaaronson.com/ ), so hopefully it's as accurate an intro to quantum computing as any webcomic could be.
N. David Mermin's "Quantum computer science: An introduction" is also a really good text for people with a CS background. It's a dead-tree book but I think the lecture notes he used to make the book are free online.
Agreed - I used Mermin's book in my undergrad. Not as comprehensive as Nielson and Chuang, but I love Mermin's style. The lecture notes you mentioned are here: http://www.lassp.cornell.edu/mermin/qcomp/CS483.html
I hate to be "that quantum consciousness guy", but one of the first sentences of the first lecture stood out to me:
For a computer to be a quantum computer the physical systems that encode the
individual bits must have no physical interactions whatever that are not under the complete control of the program.
What if we relaxed/paraphrased this as:
For a biological system to be a mind the physical systems that underlie the mental substrate must have limited/circumscribed physical interactions that are not under the complete control of the mind.
Yes, linear algebra (and complex numbers) are necessary. Though, complex numbers are fun on its own, and linear algebra is crucial for other cool things, e.g. artificial neural networks.
Looks like really solid work on the math end, with good explanations. If I may, the profanity seems gratuitous, however. Also, since a book recommendation is in part a reflection of the reader, it would be difficult to recommend this text to a colleague. Maybe something to consider.
ETA: reminds me of Tim Pope renaming Vim Foreplay to Vim Fireplace a few years ago. Apparently, that really helped him [1].
Do you mean the title or the content of the book? I'm asking because I thought the main LA content is rather clean—the first book on MATH&PHYS had much more of the "juvenile" stuff. Also is bullshit really that bad? I never saw it as a swearword, but I guess it's borderline...
You're not the first to point out the limited recommendation potential. At the same time, I think the title is really what makes people stop and look in the first place. There are so many good math, physics, and LA textbooks out there, so it's important to stand out. I'm thinking I might release a PG13 version that cuts down on the edgy subjects, but I fear something will be lost in the process...
Ivan, thanks for writing this book on Linear Algebra. It's been a while since I took a course in it and your book looks perfect for a thorough review. I'm writing this as someone that loves mathematical rigor and intends to pursue a PhD in Computer Science. I'll read every chapter of this book and can't wait to get to the chapter on QM applications.
> It is estimated that 2048-bit RSA keys could be broken on a quantum computer comprising 4,000 qubits and 100 million gates. Experts speculate that quantum computers of this size may be available within the next 20-30 years.
I think it's possible we'll have a 4,000 qubit quantum computer by 2030 if a 50-qubit one is released this year, and if quantum computers can also follow a "Moore's Law" of sorts. At least D-Wave seems to be doing it - from 28-qubits in 2007 to 2,000 in 2017.
I imagine the NSA/Russia/China would be interested in decrypting communications of at least some people even 15 years after they happened, and they could find some use for them. We already know they intend to store encrypted data indefinitely and they just add new storage for the newly obtained data rather than overwriting the old one.
On that note though, exactly how much encrypted data do they intend to store? You could probably thwart it by sending tons and tons of noise for a small signal. Do they have more storage than Amazon? This stuff isn't free.
Anyone know how big a number you can factor with 32 and with 64 qbits? Those qbit goals were a tangible thing that jumped out at me when I scanned the article.
Depends what you mean by qbit. If you are including a magic state factory in your architecture then lots and lots (millions). If you mean stable qbits then I've been told that 4096 bit numbers could be factored with 8000 qbits that are very stable and can be operated on frequently.
This isn't really true. Quantum computation devices are not general-purpose computing chips, like the way an x86 or ARM core is. They are constructed to solve specific instances of specific categories of problems in a way that is more efficient than a classical computer. And you can't accelerate all forms of computation in this way either -- only some very special categories of problems.
A "quantum computer" is more likely to look like a CPU/GPU combo where a general-purpose classical chip does the work of arranging work units for a special-purpose quantum accelerator, and interpreting the results.
I'm not making that distinction either. Quantum computation by its very nature requires special-purpose constructions. There is no such thing as a "general computation" quantum computer. Conceivably there could be a reprogrammable quantum computer able to be reconfigured to handle many different types of computation, but that would be more analogous to an FPGA than a general-purpose CPU.
That link indicates otherwise. Quantum computation is at most a superset of classical computation; every classical Turing machine is also a quantum Turing machine; the states and transitions are just purely classical.
You are probably getting down-votes because it's not a comment that contributes to the discussion. And to a lesser extant, because general-purpose computation has no monopoly on the word "computer."
As I'm completely unfamiliar with the subject, I'm having a hard time wrapping my head around what kind of impact a big development in quantum computing would have. From what I read in the Wikipedia article, it can destroy a lot of our existing crypto, and I can guess at the consequences of this.
Taking a very long-term timeline into consideration, would it be speculated that quantum computers would ultimately replace traditional computers? Are there categories of problems for which it would be worse to use a quantum computer?
A friend of mine worked on adiabatic quantum computers at D-Wave for a few years. My understanding (which may be incorrect) is that the speedups are things like take 2^n algorithms and make them 2^(sqrt(n)) instead. It's still exponential, but it's a huge improvement when n hits 100.
Will these replace traditional computers? Probably not. But you can bet there will eventually be cloud services that you submit very hard jobs and it spits back an answer faster than any traditional computer could.
I'm cautiously optimistic, but I get the impression that this is another one of those "date('Y') + 1 will be the year Linux goes mainstream on desktops" situations.
Quantum computers have come leaps and bounds in the past few years. Especially impressive is research into improving the signal-to-noise ratio of qubits through "dressing" them in microwaves[0].
Despite this, quantum computers still aren't, in the overwhelming majority of cases, better at solving problems than classical machines. Some work still needs to be done in terms of getting better signal-to-noise in qubits, as well as in terms of getting more performant hardware in the processors themselves.
And before there can be an industry built around quantum computers, there'll likely need to be some new way of keeping quantum processors running without having to keep them in a fridge at near-absolute zero.
Again, though, I'm hopeful that QC starts becoming more mainstream soon.
124 comments
[ 2.9 ms ] story [ 217 ms ] threadI'm no expert, but at the very least I believe it's recognized that some subset of NP problems, perhaps not NP-hard, should be solvable as if they were polynomial, using quantum computers.
That said, my knowledge of this subject starts and ends with things I've read on the internet, so I could be mistaken. Either way, this[1] was a very interesting introduction to some of the implications/concepts that are involved with this.
1: http://www.scottaaronson.com/papers/philos.pdf
P is a separate class from the class of problems considered efficiently solvable; BQP is the class of problems that are efficiently solved by quantum computers, and it is believed that BQP is strictly larger than P.
The missing word here is "efficiently": all problems in NP are solvable.
http://www.scottaaronson.com/blog/?p=2555
Simulated annealing is just an optimization. I use it for modelling human motion. You have the position and acceleration of each bone in the legs and feet. You start by deciding on a variable (say, reducing energy expenditure for gait), and then letting the algorithm alter variables and attempt to minimize a variable.
So if quantum annealing is anything like simulated annealing, you aren't "solving" for a single, correct answer, but getting a solution that minimizes or maximizes an outcome faster than brute force.
So a quantum computer could solve "What is the factorization of this huge number?", while quantum annealing could solve "Given these 30 different engine configurations, which combination of intake pressure, fuel flow rate, turbocharger performance curve, and engine timing would result in the best fuel efficiency?"
Here's a value of the fuel efficiency; find me a setting of the parameters that achieves a fuel efficiency better than that.
It's now a search problem. To find the best fuel efficiency, just binary search over possible values of the efficiency.
Where D-Wave differs is that you can only solve a particular kind of optimisation problem, and this kind of problem can't encode general computation. General quantum computers can solve general computation problems, not just the simulated annealing of D-Wave QC.
D-Wave markets themselves as having hundreds or thousands of qubits, but these qubits aren't easily controllable or measurable in ways that would allow Shor's to be executed on them (for example), so at the least, it seems like dishonest marketing. In order to build a general quantum computer, you need to be able to apply gates to arbitrary collections of qubits.
I'd recommend everyone to check out IBM's online http://www.research.ibm.com/quantum/ for a brief tutorial on how you need to be able to wire qubits together, and what a general quantum computer would look like. (You can even execute the result on an actual Quantum Computer; so it gives some idea of what an API would look like).
Furthermore, AI is very different from the fundamental research underlying quantum computing.
I've just completed a PhD in this area, and I've never heard this sentiment before. It seems quite unlike fusion research, which is famously always 50 years (?) away. Quantum computing research is proceeding at a rapid pace, and actually it is perhaps only 20 years old in total. Although Feynman considered something akin to a quantum computer in the 80's, it really wasn't until the 90's that quantum error correction became a thing. So it really is a very young field of research. The "old-timers", they are all about 40 years old now, unlike other areas of physics where the oldies really are very old!
But these guys transferred sideways to (aka. invented parts of) quantum computing.
I'd really like to work for one of the quantum computing companies (Rigetti, etc.) or research groups (QuAIL), but I'm not really sure how to proceed in applying to these places given that my background isn't exactly quantum computing research. Since you have experience in this area, would you have any tips on how to apply to one of these groups? My current line of thought is to just apply directly via their websites, and if I don't hear anything back, begin contributing to the relevant Github quantum computing projects as proof of capability. Would you have any suggestions for a better approach?
If you or anyone else with similar background is looking to get into quantum computing, then send along your resume at will@rigetti.com
Close. It's been 10 years away for 50 years. :)
(Although more like 65 now).
From their website it seems that they use a 3D cavity approach to quantum computing, which is (or at least was) pursued by IBM as well. Here, instead of using superconducting resonators on a chip, you use superconducting 3-dimensional cavity resonators (typically made from Aluminium) in which you place "naked" qubits that are fabricated on a Sapphire substrate. The advantage of this is that the attainable quality factor of the cavity is much higher than for a coplanar waveguide resonator (although those resonators have caught up quite a bit thanks to work that was done e.g. by the Martinis lab), and that there are fewer noise sources around the qubits.
Personally my current bet would be on Martinis or Schoelkopf to win the race, as they have the best access to both funding (though I don't know the funding details of QuantumCircuits) and Academic resources. Most of the original work on Transmon-based qubits was done at the Schoelkopf lab, and it seems that he has excellent technicians on his team.
In general though it still seems more probable that a ion-based quantum computer will be the first "real" quantum computer, as the technology is more mature and (for small numbers of qubits at least) easier to scale.
Exciting times!
https://newsroom.unsw.edu.au/news/science-tech/quantum-compu...
https://newsroom.unsw.edu.au/news/science-tech/quantum-compu...
I'd much rather ultimately see silicon-based quantum computers, which may eventually become advanced (streamlined) enough to be used by mainstream users, too. Quantum computers using superconductors and liquid nitrogen will never become mainstream. They would just be used by corporations and governments.
So I hope there will be more investing in silicon-based quantum computing research sooner rather than later. Or if not silicon, at least another material that could one day become as cheap and practical.
EDIT: As for who will be the "first" with a practical quantum computer, it does seem like Google will be the one to release a 50-qubit computer this year or the next [2]. There are like 10 other companies that have built 5-qubit quantum computers, but that was still mainly a science experiment to prove that a quantum computer can be made at all.
A 50-qubit quantum computer would establish a new threshold and according to Martinis [3], at least, it should be easier to scale from that point forward. In other words, the "quantum era" may actually begin then. I imagine those "stuck" at 5-qubits still have a long way to go before they can scale quickly beyond that.
[1] http://www.theaustralian.com.au/higher-education/new-spin-on...
[2] https://www.technologyreview.com/s/602283/googles-quantum-dr...
[3] https://www.wired.com/2014/09/martinis/
Really the only game in town currently for room-temperature quantum computing are impurity centers in diamond (most commonly nitrogen-vacancy centers). Unfortunately, there are still many difficulties there, especially since nanofabrication of diamond and precise implantation of the impurities is still a new field.
What does this even mean in this context?
My understanding (which is limited!) is that there are some apparently NP-complete problems that are P for a quantum process.
Now, it may be that these problems were never actually NP-complete, but are a superset of P for quantum computers.
Or it may be that quantum computers can really solve some NP-complete problems in P time.
Either way though, it isn't a consequence of CPU-cycles per se, but the underlying mathematical distinction (ie, what a silicon vs quantum computer does, not what it can do in a "cycle").
As it stands, quantum computers can solve some problems faster than classical computers currently can; factorisation, discrete log and other problems with a particular kind of repeated structure are some such problems. However, we do not know for certain that these problems are not efficiently solvable using classical computers (I'd bet that factorisation will be put in P within my lifetime).
A big goal of the QC community is to demonstrate quantum supremacy: to unconditionally show that quantum computers can solve a problem with fewer resources than classical computers. We've made progress on this (check out Scott Aaronson's blog for more info), but still haven't achieved it.
Lastly, a small nitpick. "P time" is not a meaningful phrase; P is a complexity class consisting of problems solvable efficiently (i.e., in polynomial time) on classical computers.
The class of efficiently solvable problems on quantum computers is BQP: Bounded-error Quantum Polynomial-time, which means that BQP is the class of problems that are efficiently solved by a quantum computer, but only with some probability bounded away from 1/2. This means the QC can return incorrect answers, but there are techniques to reduce the error probability to extremely small values.
The classical analogue of this class is BPP, which is Bounded-error probabilistic poly-time. There's a conjecture that BPP=P, and if we have any sort of crypto then the conjecture is true.
> there are some apparently NP-complete problems that are P for a quantum process
The definition of P refers to deterministic machines; no quantum. 'P for a quantum process' is a meaningless phrase. Problems solvable in polynomial time by quantum computers are contained in the classes EQP (if the answers are to be always correct) and BQP (if the answers are to be correct with a probability which may be made as high as desired).
> it may be that these problems were never actually NP-complete, but are a superset of P for quantum computers.
'NP-complete' is not an exact synonym of informal concepts like 'hard' or 'intractable'. It has a precise definition: NP-complete problems are those for which are simultaneously NP (the solution can be verified in polynomial time) and NP-hard (every instance of any NP problem can be reduced in polynomial time to it). There are problems that have been proved NP-complete. For others there are no known polynomial time algorithms, but they are suspected not to be NP-complete either. If P = NP, the notion of NP-completeness becomes trivial and equivalent to simply being in P. There's no way a problem now known to be NP-complete will later be shown not to be.
> Or it may be that quantum computers can really solve some NP-complete problems in P time.
This has not been proved false, but generally considered unlikely. (Also, 'some NP-complete problems' would imply 'all of them', by the definition of NP-completeness.)
Another class of algorithms use quantum computers as simulators (e.g. for chemical simulations). You can also encode certain optimization problems as "constraints" in a quantum system and hope that quantum dynamics will find good solutions to the optim. problem faster.
[1] https://en.wikipedia.org/wiki/Grover%27s_algorithm
[2] https://en.wikipedia.org/wiki/Shor%27s_algorithm
[3] https://en.wikipedia.org/wiki/Quantum_algorithm_for_linear_s...
Yeah it really is. Quantum states just do not even fit in classical memory. Like, exponentially so. The parent was specifically asking about "possibility" not speedup.
One of the first things proven[1] about BQP is that it's contained in P^#P, which is contained in PSPACE. That means a Turing machine can simulate any quantum computer with only polynomial space (but possibly very slowly).
[1] http://epubs.siam.org/doi/abs/10.1137/S0097539796300921
Calling it a speed up is kinda correct but seems slightly wrong to me. It is a completely different computing model which tends to use different algorithms that make solutions to certain problems feasible on a quantum computer that aren't on an equally powered classical computer. That is why it's so powerful, but at the same time, classical computing could stay "faster" than quantum computing for a long time, or even forever.
Most concepts carry over, but some just don't make sense anymore, and a lot of effort must be invested into fundamentally new click-clack (or zip-zap) arrangements to get things done. A large part of the "intelligence" in the final system is actually latent in its structure.
Shameless plug: I wrote a linear algebra book that discusses applications to quantum mechanics, including quantum computing. Check out an extended preview here: https://minireference.com/static/excerpts/noBSguide2LA_previ... Available electronically here https://gum.co/noBSLA and the print version is coming soon.
Edit: just to elaborate on this. I hear often from people "what math do i need to learn so i can do X?" And I just think that alot of the time people should just do X and this will force them to figure out the math as needed. Learning math from a book is brutally difficult! Just like learning a programming language, what is the best way to do that? You start with a project that you want to do. People who want to read the "pre-requisite book" often-times just seem to be deferring the real crunch that happens when you actually get down to the business of actually learning X.
Excellent flick. If you haven't seen it, I recommend giving it a watch.
greenaddress.it
N.B. My maturity level is normally only a half step above the average 12-year-old. I can play this game all day ;)
Understanding diagonalization (and more generally, spectral theory), scalar products, and norms would be a great start. Then you can pick any quantum information textbook.
https://graybits.biz/notes/quantum_mechanics/preface
It was a collaboration with Scott Aaronson ( http://scottaaronson.com/ ), so hopefully it's as accurate an intro to quantum computing as any webcomic could be.
What if we relaxed/paraphrased this as: For a biological system to be a mind the physical systems that underlie the mental substrate must have limited/circumscribed physical interactions that are not under the complete control of the mind.
Yes, linear algebra (and complex numbers) are necessary. Though, complex numbers are fun on its own, and linear algebra is crucial for other cool things, e.g. artificial neural networks.
ETA: reminds me of Tim Pope renaming Vim Foreplay to Vim Fireplace a few years ago. Apparently, that really helped him [1].
1. https://github.com/tpope/vim-foreplay
You're not the first to point out the limited recommendation potential. At the same time, I think the title is really what makes people stop and look in the first place. There are so many good math, physics, and LA textbooks out there, so it's important to stand out. I'm thinking I might release a PG13 version that cuts down on the edgy subjects, but I fear something will be lost in the process...
https://security.stackexchange.com/questions/87345/how-many-...
I think it's possible we'll have a 4,000 qubit quantum computer by 2030 if a 50-qubit one is released this year, and if quantum computers can also follow a "Moore's Law" of sorts. At least D-Wave seems to be doing it - from 28-qubits in 2007 to 2,000 in 2017.
https://en.wikipedia.org/wiki/D-Wave_Systems
I imagine the NSA/Russia/China would be interested in decrypting communications of at least some people even 15 years after they happened, and they could find some use for them. We already know they intend to store encrypted data indefinitely and they just add new storage for the newly obtained data rather than overwriting the old one.
On that note though, exactly how much encrypted data do they intend to store? You could probably thwart it by sending tons and tons of noise for a small signal. Do they have more storage than Amazon? This stuff isn't free.
A "quantum computer" is more likely to look like a CPU/GPU combo where a general-purpose classical chip does the work of arranging work units for a special-purpose quantum accelerator, and interpreting the results.
How quantum computers are deployed in the real world is irrelevant to the theoretical study...
That link indicates otherwise. Quantum computation is at most a superset of classical computation; every classical Turing machine is also a quantum Turing machine; the states and transitions are just purely classical.
Taking a very long-term timeline into consideration, would it be speculated that quantum computers would ultimately replace traditional computers? Are there categories of problems for which it would be worse to use a quantum computer?
http://www.scottaaronson.com/blog/
Will these replace traditional computers? Probably not. But you can bet there will eventually be cloud services that you submit very hard jobs and it spits back an answer faster than any traditional computer could.
Quantum computers have come leaps and bounds in the past few years. Especially impressive is research into improving the signal-to-noise ratio of qubits through "dressing" them in microwaves[0].
Despite this, quantum computers still aren't, in the overwhelming majority of cases, better at solving problems than classical machines. Some work still needs to be done in terms of getting better signal-to-noise in qubits, as well as in terms of getting more performant hardware in the processors themselves.
And before there can be an industry built around quantum computers, there'll likely need to be some new way of keeping quantum processors running without having to keep them in a fridge at near-absolute zero.
Again, though, I'm hopeful that QC starts becoming more mainstream soon.