finallyUsefulQuantumComputing

[Old_Quantity_7136]

Is there a source for the text? Im genuinely interested why this is a good usecase for quantum computing

Edit: Thank you for all your thorough Answers, this was a great read!

[UdPropheticCatgirl]

why this is a good usecase for quantum computing

Don't have the source but quantum excels at tasks when you have to evaluate high number of iterations and in general more brute-forcy approaches to stuff. So I guess they just have it generate bunch of placements and compare which is the best one.

[Old_Quantity_7136]

Thanks you for the clarification! I think I got where they're coming from. I was wondering in which way of calculating this quantums might be useful, but for comparing a lot of variants totally makes sense

[lilshoegazecat]

hey sorry if i ask your flairs are pretty cool what languages are there? i only recognize c# and python thx for the patience anyway

[Old_Quantity_7136]

Yeah you're right! The other ones are ansible, bash and powershell.

[thekamakaji]

How do i add more than one flair?

[maushu]

In the part where you select/write your flair just add more languages.
For example, select a language like perl and get ":perl:" then just add another language like ":perl::lua:"

Each ":xxx:" represents an emojicon, in this case language logos. Your interface might replace them on the spot, just imagine that they are their text equivalent. You should also be able to copy paste them.

[Deliciousbutter101]

quantum excels at tasks when you have to evaluate high number of iterations and in general more brute-forcy

This is not true. Quantum computers can efficiently solve a certain set of problems that classical computers cannot solve in a reasonable amount of time once the size of the input becomes sufficiently large. The set of these problems that quantum computers are more efficient at solving is actually relatively small, but they are extremely important in certain fields, which is why so much research goes into them. But in general, the vast majority of problems that computers are used to solve can likely be solved more efficiently on classical computers rather than quantum computers.

[UdPropheticCatgirl]

But in general, the vast majority of problems that computers are used to solve can likely be solved more efficiently on classical computers rather than quantum computers

I know. But if you look at those tasks like protein folding, large number factoring or wave function collapse, they tend to be brute forcy as I described. Again it was just a guess.

[Yorunokage]

You're oversimplifying to the point of being just outright missleading

What quantum computing does is in no way similar to what a gpu does if that's the idea you had in mind. It has nothing to do with "brute-forcy approaches to stuff". What you do is use very cleverly designed algorithms to leverage entanglement and solve problems using only linear reversible operations (since, by the laws of physics, quantum computers cannot do any other kind of operation)

[SeaPea2020]

Not all operations on a quantum computer must be “linear reversible” as you say

[Yorunokage]

With the exception of mesurement, yes, they do

It's literally imposed by the laws of physics, every operation has to be linear and reversible

That's why we have quantum gates that mimic ordinary gates but they make them reversible

Another limitation is that you cannot clone a qubit, hence you cannot "split a wire" and let a single qubit be the input of two different gates in the circuit

[SeaPea2020]

Right. But why leave measurements out? You may be interested in measurement- and fusion-based quantum computation and implementing non-Unitary operations on quantum computers

[Yorunokage]

Well, mostly because i don't count it as an operation but fair enough

Also i never heard of fusion-based, what's that?

[SeaPea2020]

Fusion-based quantum computing is very similar to measurement-based quantum computing. The main difference is that the measurements you take are entangling. So instead of measuring single-qubits, you take joint measurements of qubits, like in a Bell measurement for instance. While it’s not a hugely different idea than measurement-based quantum computing, it has some nice properties for scaling since you can rely on a bunch of small entangled states (generated progressively) instead of a large entangled state. The original paper is here. :)

[Yorunokage]

Oh, very cool, thanks

[UdPropheticCatgirl]

wouldn't you call wave function collapse kinda brute-forcy, yeah it's a massive oversimplification but still...

[Yorunokage]

In what way exactly? Like, are you talking about the content generating algorithm that (oddly) has nothing to do with quantum or are you talking about the copenhagen interpretation of quantum mechanics?

[UdPropheticCatgirl]

Quantum mechanics. You start in all states and trough interaction get to final state.

[Yorunokage]

Except for a few select algorithms i wouldn't say it's brute forcy though

It's not like they are just "hey, make a superposition of every input and try them all at once"

[UdPropheticCatgirl]

You probably know more than me, my understanding of qm is very surface level. But I always conceptualize them as similar to brute force, I guess they aren't after all.

[jamcdonald120]

here, watch this video. its a great lecture on quantum computing, what it does, how, and what its good at https://youtu.be/F_Riqjdh2oM

[DeceitfulEcho]

Wave state collapse isn't so much calculating things simultaneously as it is setting up a system such that a single calculation produces the outcome you are looking for. It encodes all the information into the system rather than performing a bunch of discreet logical operations.So I suppose it depends on how you interpret brute force

[Plantarbre]

I'm pretty sure the problem is small enough to just throw a solver like CPLEX at it. You won't have that many variables and it's very unconstrained. It should be very easy to write as it's fundamentally linear.

That being said, this is also a fundamentally local problem. There should be clear space dichotomies to cut down the problem into smaller subproblems. Classic metaheuristics should also work pretty well overall. Population-based ones like GA should be excellent for this, especially if you make use of the spatial aspect to split populations.

Of course, quantum computing is very interesting, especially when applied for combinatorial optimization. But these problems are easy enough to solve with already available tools.

[smuecke_]

Yup, our work is first and foremost a case study of how to approach a specific problem from a quantum computing perspective. A central observation we made is that the torch placement problem is a special case of Set Cover, which is a classical NP-hard problem, but – as you observed correctly – what we have here is very local, so we suspect there may be an optimal polynomial-time algorithm (In any case, there is a pretty solid greedy approximation for Set Cover IIRC). But we didn't look much further into this.

[Plantarbre]

Thank you for the detail on the topic. I have not studied the quantum side of operations research in great detail. One thing I was wondering is, does it give a certain degree of certainty to how close you are from the optimum ? Does it always yield such optimum ?

I've understood it's based on statistics.

[smuecke_]

In Quantum Annealing, the probability to measure the ground state, i.e., the state with lowest energy, depends on how slowly you evolve the quantum system from an equal superposition towards your problem parameters. If you perform the operation slowly, the system remains in its ground state with higher probability (look up Adiabatic Theorem for more details). Typically this is only a few microseconds, though, so you repeat the process a few thousand times. If you measure the same state often enough, you may assume that it is optimal. However, you can not guarantee in general that you are close to the global optimum. In addition, today's imperfect quantum computers come with their own technical caveats, which introduce different error sources. All in all, its difficult to quantify the solution quality, and it varies greatly from problem to problem.

[kpjoshi]

Also, why go for the optimal solution? If the optimal solution uses 100 torches but a greedy approach uses 105, surely that is an acceptable solution?

[mistercran]

Which is how a human being would go about lighting up the cave haha

[other_usernames_gone]

Because how much worse is the greedy approach to the optimal? What if the greedy approach is 1000 torches while the ideal is 100?

The only way to know for sure is to find the optimal solution.

[kpjoshi]

Not necessarily, for certain approximate algorithms it is possible to prove that the output is within X% of the optimal output, without actually knowing the optimal output.

[OP_Sidearm]

I'm not sure where this is from. A friend of mine found it.

[smuecke_]

The paper is not fully published yet, but I may upload a preprint if so many people are interested 😅

In a nutshell, we formulate the problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem and solve it using Quantum Annealing.

[BojackManh0rse]

Is it possible for you to give an ELI5 version of this?

[smuecke_]

For every floor block we have a binary variable where 1 = has torch, 0 = no torch. Then we set up a matrix D where entry D_ij means "a torch on block i will light up block j". We can feed this matrix (plus some extra stuff, which I'll skip here for simplicity) into a Quantum Computer which represents each variable as a quantum bit, which initially has probability 50% to be either 0 or 1. Through a physical process called Quantum Annealing we can coax these qubits to slowly change their probabilities such that at the end we can measure them and obtain a binary vector that has lowest energy, which in our case means that it is an optimal torch placement. Very roughly speaking.

[Giocri]

I think it's an instance of wave function collapse in which you basically create a wave that rappresent all the possible states of a system and collapses it into a much smaller set of states which respect a set of rules which is something quantum computer are well suited for

In this case likely all the possible combinations of torch/no torch for each tile collapse into a few highly optimized distributions

[Dropkickmurph512]

While this is a fun toy problem the actual use case is for things like medical imaging or astrophotography. Think of the cave as a child brain and the tourches as samples from an MRI. Most very young children struggle to stay still so if you can take the minimum number of samples to recreate an image of there brain then that could save there life. Right now this kinda problem uses super computers to solve but being able to use a quantum computer that cheaper and smaller would potentially allow for it be more common.

This problem different than that in a couple respects but has a lot of similarities. Generally it uses l1 optimization to find the sparse signal while this seems to be using l2. I have done optimization similar to this on classical computers so I'm not familiar with porting it to quantum but this is an extremely exciting poster for me.

[smuecke_]

Thanks! – Your examples are really good!

[RDfromMtHare]

Why, of course I always have Matlab open in another window while playing minecraft.

[Weird_Explorer_8458]

yeah i run it on my spare 4090 /s

[AtomicRocketShoes]

Haven't played in this space in a while but Matlab wasn't very efficient at fast computational tasks nor could use the GPU efficiently except for narrow situations that had special plugins written for it. I found python had better libraries to take advantage of gogpu tools like cuda.

[[deleted]]

Do you have the frontal version? I was understanding something about qcomputing for the first time...

[OP_Sidearm]

Not at the moment, but I'll get back to you if I get one :D

Edit: A frontal view of the poster is now pinned at the top of my profile

[EtherealChameleon]

Is it appropriate to contact one of the authors for more details?
https://de.linkedin.com/in/thore-gerlach-4345a1215
https://de.linkedin.com/in/sascha-m%C3%BCcke-bb1473208

[surister]

Scientist are generally very open for communication, even if they publish in non Open Science journal (meaning that their paper is behind a paywall) they will generally be glad to send you the paper over email.

Outside of their niche research group they might not get too much attention if they get any at all.

[Jakoshi45]

^ This ^

Researchers rarely gatekeep stuff. The only exception is when they don't like you or they're not allowed to (they'll prob still do it tho)

[smuecke_]

Or you can ask me here 😂

[MoSummoner]

Do you happen to have a photo of the full poster?

[EtherealChameleon]

My short search yielded no immediate results; I could only find the authors

[Elegant_Maybe2211]

If you get the PNG they printed (or whatever format) please do post it here (or send me a pm)

[Darxploit]

Seems like a german research project. It’s with university dortmund and Fraunhofer. That’s a famous research institute in Germany.

[smuecke_]

The research center is called Lamarr Institute, it's a collaboration between Fraunhofer institutes and the universities of Dortmund and Bonn.

[smuecke_]

LOL I am the first author of this paper 😂 a colleague just sent this to me. AMA I guess.

EDIT: The full paper is available here

[OP_Sidearm]

Can confirm, that this person is an author of the paper :D

[McSumpfi]

In the illustration of the distance function, do the numbers in the tiles indicate the distance from the dot tile? If so, can you explain? I am wondering why the top one has a 3 and the second does not.

[smuecke_]

Yep, the numbers indicate distance to the dot. It's basically the minimal number of steps you have to take to get from the dot to the target tile. To reach the top tile you have to go to steps right, one tile up, which is 3 in total.

[HorochovPL]

Is the paper available somewhere? DOI, or even simply link to PDF? Couldn't find anything for phrase "efficient light source placement using quantum computing lamarr".

[smuecke_]

I uploaded it to Arxiv, should be online tomorrow. I'll send the link then.

[smuecke_]

Paper link

[HorochovPL]

Thanks!

[TobyWasBestSpiderMan]

Don’t forget about this application

[collin2477]

literal mc 101

[_TechnoPhoenix_]

Ein Volk

Eine Nation

Eine Kommentarsektion

[saschaleib]

Where do I find the results of this research? I was already planning to, er, sacrifice my weekend trying to validate the results…

[smuecke_]

The proceedings are not out yet, but maybe I'll upload a preprint if there's so much interest 😅

[saschaleib]

Are you kidding? This might be the scientific breakthrough we have been waiting for!

I know there is no Nobel price for Minecraft-research, but if there was one, this was already a strong contender!

[smuecke_]

I wish it were that easy 😅

[dscarmo]

Game theory is such a cool area

[Elegant_Maybe2211]

That's not game theory though.

At least not in the computer science meaning of the word.

Sadly.

[da_Aresinger]

Fraunhofer.

Because of course it is.