Login
You're viewing the discuss.systems public feed.
  • Søren Fuglede Jørgensenfuglede@mastodon.social
    Nov 2, 2026, 11:45 AM

    Suppose that you are given the following problem: Given a collection of points in a square grid in a plane, and a specified start and end point, can you find a path in the grid that goes through every point exactly once, and without vising any other points? Here's an example; can you go from 𝑠 to 𝑡, moving along the grid, visiting each blue grid point once, but never touching any of the other grid intersections?

    1/10

    #math #compsci #quantum

    Four points in a square grid.
    💬 1🔄 4⭐ 4

Replies

  • Søren Fuglede Jørgensenfuglede@mastodon.social
    Nov 2, 2026, 11:46 AM

    Here's the solution. Did you find that too? If so, good job! In general, given an arbitrary collection of points like that, the problem turns out to be hard. Itai et al showed in 1982 that the problem is what computer scientists would call NP-complete.

    Let us look at an incredibly convoluted way of solving it by relating it to quantum circuit optimization!

    The solution to the problem from before.
    💬 0🔄 0⭐ 0