6 ms·

Understanding quantum computing through drunken walks

61 points by nsoonhui 6y ago

drdeca 6y ago
I'm a bit unclear about what the process they are using for the quantum random walk. Like, after 2 steps, what is the state that it is in? Presumably not just (1/2)|-1> + sqrt(1/2)|0> + (1/2)|1> , because then that would seem to just give the same behavior as the classical random walk. The linked code has a Hadamard gate, which it cnot's onto some other qubit, and then negates, and then cnots onto some third quibit. Ah, the wikipedia article at https://en.wikipedia.org/wiki/Quantum_walk https://en.wikipedia.org/wiki/Quantum_walk makes what it is describing much clearer!
- Strilanc 6y ago
  Yeah, the descending arrows diagram they show in the post can't be correct because there are cases where two outputs overlap at only one spot. That makes it impossible for them to be orthogonal which breaks reversibility.
  - eigenket 6y ago
    I think thats fine, you just need the spin (what gets calls the "coin") degree of freedom states to be orthogonal for the bit that came from the left and the bit that came from the right. A quantum walk with a unitary like U = sum_i |0><0| ⊗ |i><i+1| + |1><1| ⊗ |i><i-1| where the first Hilbert space is a qubit and the second is L^2(Z), an integer-valued "position". Will do this. Two states |a>|-1> and |b>|+1> will after one time step find themselves overlapping at exactly one lattice point (at |0>) but the coin degrees of freedom will keep them orthogonal. Edit: in case of unicode issues the "⊗" symbol is supposed to be \otimes, a tensor product.
    - Strilanc 6y ago
      In a quantum walk the locations typically correspond to states, not to qubits. You're right that turning them into qubits would allow the diagram to work, but then I don't think it would match up with the "vampire fangs".
      - eigenket 6y ago
        I don't understand this comment at all. Let me clarify my point slightly. The quantum walk is a unitary operator acting on a Hilbert space H consisting of two parts H_spin and H_space H = H_spin ⊗ H_space In this example H_spin is just a qubit and H_space is L^2(Z). In my example above the |0><0| and |1><1| are projectors acting on the spin degree of freedom (the first Hilbert space) and the sum_i |i><i+1| and sum_i |i><i-1| are shift operators acting on the space degree of freedom (the second Hilbert space). If you take the unitary I wrote and do the iteration U (H⊗I) U (H⊗I) U (H⊗I) U (H⊗I) ... U (H⊗I) where U (H⊗I) is the Hadamard operator on the spin Hilbert space and I is the identity on the space part you get exactly the quantum walk that gives the "fangs" picture.
        Strilanc 6y ago
        Sorry, I misread your comment initially. Yes, if you have an additional degree of freedom that is not being plotted (a coined walk), then the overlap is fine.
        eigenket 6y ago
        If there is no additional degree of freedom the walk has to be trivial (assuming homogeneity).
        Strilanc 6y ago
        In a coined walk you apply a hadamard to the least significant qubit of an integer register, then increment the register, hadamard the least significant qubit, decrement the register, and repeat. Although there is no additional degree of freedom, you are alternating between two non-commuting effects.
        eigenket 6y ago
        This seems completely different to the sorts of walks I'm used to. When you say "qubit of an integer register" what are you actually talking about here? Do you have a qubit for each integer like a spin chain or something? The sorts of quantum walks I'm used to are exactly the ones in the article and are also mentioned in the wikipedia page here. https://en.wikipedia.org/wiki/Quantum_walk#Discrete_time https://en.wikipedia.org/wiki/Quantum_walk#Discrete_time The example given on the wiki page is the classic example that gets called a "coined walk" in the literature.
toomanybeersies 6y ago
I just recently found out that AWS Braket exists [1], which is a "fully managed quantum computing service", complete with actual quantum computers. I've been trying to find a use case for it at work, purely so I can add "developing business solutions utilising quantum computing technology" to my resume. [1] https://aws.amazon.com/braket/ https://aws.amazon.com/braket/
- eigenket 6y ago
  IBM also have stuff for this based on the qiskit project. I don't know anything about the software interface for the amazon thing at all but I think IBM's quantum computers are generally considered better than the Rigetti ones that amazon is selling time on (this is almost entirely based on hearsay and one talk I saw by a team working with Rigetti). At least a lot of researchers I know use the IBM stuff. I have never even heard of IonQ before, so I can't comment on them.
- hutzlibu 6y ago
  Has there actually been any use case found, for any real work, with current quantum computers? I am sorry for potential ignorance and I don't understand much of the topic, but everytime I read about it, it got the message, that it will be awesome, very soon. But currently mostly research. I mean it really surprise me, that it already exist as a service, so there must be real use cases already? Or is this service directed at research? (real use cases, too, sure, but in a different sense)
  - fsh 6y ago
    Current quantum computers are way to small and noisy for any practical applications. To give an example, the largest number ever factored using Shor's algorithm on a quantum computer (without cheating) is 15. These cloud services might be useful for researchers to test possible algorithms on. On the other hand, FOMO probably also plays a significant role in the emergence of all these quantum cloud services.
    - hutzlibu 6y ago
mikhailfranco 6y ago
I also like the paper by Marko Rodriguez that explains quantum random walks using the Gremlin graph database language: https://arxiv.org/abs/1511.06278 https://arxiv.org/abs/1511.06278 [pdf] https://www.slideshare.net/slidarko/quantum-processes-in-graph-computing https://www.slideshare.net/slidarko/quantum-processes-in-gra...
spreinhardt 6y ago
Re: use cases for quantum computing: - I spent 4 years at D-Wave and now 2 years at QCI working on apps/tools for quantum computers, mostly focused on constrained optimization. I know a fair amount about how to use D-Wave's annealing QPU and a smidgen about how to use gate-model QPUs but am not a quantum physicist. - Yes, the QPUs available via AWS' Braket are real QPUs that run real quantum problems, and cost real money. :) IBM, Honeywell, and others have QPUs available directly from the vendor. - To my knowledge there are no real-world problems that today deliver better performance quantumly than classically. (In my view, Google's quantum-supremacy demo of October 2019 was a major milestone but not a real-world problem.) - The use cases that have a chance to be useful before 2030 need to exploit noisy intermediate-scale quantum (NISQ) computers, which for gate-model QPUs means foregoing most of the digital nature of the gate model and using it like an analog computer. Or D-Wave's annealing-based QPU, which is inherently analog. - To my way of thinking, ~all near-term use cases will actually be hybrid classical/quantum, in part because today's QPUs are smaller than ~all real-world problems, and hence the attention must be on the overall algorithm and not just the QPU. - In my view, the 2 leading use cases are simulation of quantum effects and constrained optimization (and I count AI/ML as a close cousin of constrained optimization), which both can derive value from near-term QPUs. For simulation of quantum effects I'd point to the work of Andrew King et al. from D-Wave [1]. For constrained optimization I'd point to the work of Hadfield et al. [2] and Harrigan et al. [3] as well as the host of problems that have been targeted at D-Wave systems over the last few years [4]. Traveling salesperson is a good canonical problem; the constraints are to visit every city and wind up where you started and the objective function is (say) fewest miles traveled. - Here at Quantum Computing Inc., we are focused on a) constrained optimization as the most likely generally useful near-term capability, b) exposing APIs that enable subject-matter experts (in something other than QC) to use QPUs to solve real-world problems, and c) delivering strong classical performance as a building block for earliest quantum advantage, e.g. our paper on graph partitioning [5]. <shamelessCommerce> Our Qatalyst quantum-acceleration platform delivers these capabilities today, along with access to QPUs; see documentation at [6]. </shamelessCommerce> Hope that helps. Caveat: I work for a quantum-software company. [1] https://www.nature.com/articles/s41467-021-20901-5 https://www.nature.com/articles/s41467-021-20901-5 [2] https://arxiv.org/pdf/1706.02998.pdf https://arxiv.org/pdf/1706.02998.pdf [3] https://arxiv.org/pdf/2004.04197.pdf https://arxiv.org/pdf/2004.04197.pdf [4] https://www.dwavesys.com/leap https://www.dwavesys.com/leap [5] https://arxiv.org/pdf/2006.15067v1.pdf https://arxiv.org/pdf/2006.15067v1.pdf [6] https://docs.qci-prod.com/ https://docs.qci-prod.com/

61 points by nsoonhui 6y ago

I'm a bit unclear about what the process they are using for the quantum random walk. Like, after 2 steps, what is the state that it is in? Presumably not just (1/2)|-1> + sqrt(1/2)|0> + (1/2)|1> , because then that would seem to just give the same behavior as the classical random walk. The linked code has a Hadamard gate, which it cnot's onto some other qubit, and then negates, and then cnots onto some third quibit. Ah, the wikipedia article at https://en.wikipedia.org/wiki/Quantum_walk https://en.wikipedia.org/wiki/Quantum_walk makes what it is describing much clearer!

Strilanc 6y ago
Yeah, the descending arrows diagram they show in the post can't be correct because there are cases where two outputs overlap at only one spot. That makes it impossible for them to be orthogonal which breaks reversibility.
- eigenket 6y ago
  I think thats fine, you just need the spin (what gets calls the "coin") degree of freedom states to be orthogonal for the bit that came from the left and the bit that came from the right. A quantum walk with a unitary like U = sum_i |0><0| ⊗ |i><i+1| + |1><1| ⊗ |i><i-1| where the first Hilbert space is a qubit and the second is L^2(Z), an integer-valued "position". Will do this. Two states |a>|-1> and |b>|+1> will after one time step find themselves overlapping at exactly one lattice point (at |0>) but the coin degrees of freedom will keep them orthogonal. Edit: in case of unicode issues the "⊗" symbol is supposed to be \otimes, a tensor product.
  - Strilanc 6y ago
    In a quantum walk the locations typically correspond to states, not to qubits. You're right that turning them into qubits would allow the diagram to work, but then I don't think it would match up with the "vampire fangs".
    - eigenket 6y ago
      I don't understand this comment at all. Let me clarify my point slightly. The quantum walk is a unitary operator acting on a Hilbert space H consisting of two parts H_spin and H_space H = H_spin ⊗ H_space In this example H_spin is just a qubit and H_space is L^2(Z). In my example above the |0><0| and |1><1| are projectors acting on the spin degree of freedom (the first Hilbert space) and the sum_i |i><i+1| and sum_i |i><i-1| are shift operators acting on the space degree of freedom (the second Hilbert space). If you take the unitary I wrote and do the iteration U (H⊗I) U (H⊗I) U (H⊗I) U (H⊗I) ... U (H⊗I) where U (H⊗I) is the Hadamard operator on the spin Hilbert space and I is the identity on the space part you get exactly the quantum walk that gives the "fangs" picture.
      - Strilanc 6y ago
        Sorry, I misread your comment initially. Yes, if you have an additional degree of freedom that is not being plotted (a coined walk), then the overlap is fine.
        eigenket 6y ago
        If there is no additional degree of freedom the walk has to be trivial (assuming homogeneity).
        Strilanc 6y ago
        In a coined walk you apply a hadamard to the least significant qubit of an integer register, then increment the register, hadamard the least significant qubit, decrement the register, and repeat. Although there is no additional degree of freedom, you are alternating between two non-commuting effects.
        eigenket 6y ago
        This seems completely different to the sorts of walks I'm used to. When you say "qubit of an integer register" what are you actually talking about here? Do you have a qubit for each integer like a spin chain or something? The sorts of quantum walks I'm used to are exactly the ones in the article and are also mentioned in the wikipedia page here. https://en.wikipedia.org/wiki/Quantum_walk#Discrete_time https://en.wikipedia.org/wiki/Quantum_walk#Discrete_time The example given on the wiki page is the classic example that gets called a "coined walk" in the literature.

toomanybeersies 6y ago

I just recently found out that AWS Braket exists [1], which is a "fully managed quantum computing service", complete with actual quantum computers. I've been trying to find a use case for it at work, purely so I can add "developing business solutions utilising quantum computing technology" to my resume. [1] https://aws.amazon.com/braket/ https://aws.amazon.com/braket/

eigenket 6y ago
IBM also have stuff for this based on the qiskit project. I don't know anything about the software interface for the amazon thing at all but I think IBM's quantum computers are generally considered better than the Rigetti ones that amazon is selling time on (this is almost entirely based on hearsay and one talk I saw by a team working with Rigetti). At least a lot of researchers I know use the IBM stuff. I have never even heard of IonQ before, so I can't comment on them.
hutzlibu 6y ago
Has there actually been any use case found, for any real work, with current quantum computers? I am sorry for potential ignorance and I don't understand much of the topic, but everytime I read about it, it got the message, that it will be awesome, very soon. But currently mostly research. I mean it really surprise me, that it already exist as a service, so there must be real use cases already? Or is this service directed at research? (real use cases, too, sure, but in a different sense)
- fsh 6y ago
  Current quantum computers are way to small and noisy for any practical applications. To give an example, the largest number ever factored using Shor's algorithm on a quantum computer (without cheating) is 15. These cloud services might be useful for researchers to test possible algorithms on. On the other hand, FOMO probably also plays a significant role in the emergence of all these quantum cloud services.
  - hutzlibu 6y ago

mikhailfranco 6y ago

I also like the paper by Marko Rodriguez that explains quantum random walks using the Gremlin graph database language: https://arxiv.org/abs/1511.06278 https://arxiv.org/abs/1511.06278 [pdf] https://www.slideshare.net/slidarko/quantum-processes-in-graph-computing https://www.slideshare.net/slidarko/quantum-processes-in-gra...

spreinhardt 6y ago

Re: use cases for quantum computing: - I spent 4 years at D-Wave and now 2 years at QCI working on apps/tools for quantum computers, mostly focused on constrained optimization. I know a fair amount about how to use D-Wave's annealing QPU and a smidgen about how to use gate-model QPUs but am not a quantum physicist. - Yes, the QPUs available via AWS' Braket are real QPUs that run real quantum problems, and cost real money. :) IBM, Honeywell, and others have QPUs available directly from the vendor. - To my knowledge there are no real-world problems that today deliver better performance quantumly than classically. (In my view, Google's quantum-supremacy demo of October 2019 was a major milestone but not a real-world problem.) - The use cases that have a chance to be useful before 2030 need to exploit noisy intermediate-scale quantum (NISQ) computers, which for gate-model QPUs means foregoing most of the digital nature of the gate model and using it like an analog computer. Or D-Wave's annealing-based QPU, which is inherently analog. - To my way of thinking, ~all near-term use cases will actually be hybrid classical/quantum, in part because today's QPUs are smaller than ~all real-world problems, and hence the attention must be on the overall algorithm and not just the QPU. - In my view, the 2 leading use cases are simulation of quantum effects and constrained optimization (and I count AI/ML as a close cousin of constrained optimization), which both can derive value from near-term QPUs. For simulation of quantum effects I'd point to the work of Andrew King et al. from D-Wave [1]. For constrained optimization I'd point to the work of Hadfield et al. [2] and Harrigan et al. [3] as well as the host of problems that have been targeted at D-Wave systems over the last few years [4]. Traveling salesperson is a good canonical problem; the constraints are to visit every city and wind up where you started and the objective function is (say) fewest miles traveled. - Here at Quantum Computing Inc., we are focused on a) constrained optimization as the most likely generally useful near-term capability, b) exposing APIs that enable subject-matter experts (in something other than QC) to use QPUs to solve real-world problems, and c) delivering strong classical performance as a building block for earliest quantum advantage, e.g. our paper on graph partitioning [5]. <shamelessCommerce> Our Qatalyst quantum-acceleration platform delivers these capabilities today, along with access to QPUs; see documentation at [6]. </shamelessCommerce> Hope that helps. Caveat: I work for a quantum-software company. [1] https://www.nature.com/articles/s41467-021-20901-5 https://www.nature.com/articles/s41467-021-20901-5 [2] https://arxiv.org/pdf/1706.02998.pdf https://arxiv.org/pdf/1706.02998.pdf [3] https://arxiv.org/pdf/2004.04197.pdf https://arxiv.org/pdf/2004.04197.pdf [4] https://www.dwavesys.com/leap https://www.dwavesys.com/leap [5] https://arxiv.org/pdf/2006.15067v1.pdf https://arxiv.org/pdf/2006.15067v1.pdf [6] https://docs.qci-prod.com/ https://docs.qci-prod.com/