{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Wave function collapse.\n", "\n", "In the first round this will be a collection of notes on the topic of wave collapse functions. Whether I will convert it into a monograph of some kind - later - is to be decided.\n", "\n", "**The origins**\n", "\n", "To my knowledge, the idea of using wave function reduction to explain quantum measurement was first presented by Werner Heisenberg in \"THE ACTUAL CONTENT OF QUANTUM THEORETICAL KINEMATICS AND MECHANICS\", original title: \"Uber den anschaulichen Inhalt der quantentheoretischen Kinematik und Mechanik\", Zeitschrift fur Physik, v. 43, no. 3-4, pp. 172-198, 1927. Available [here](https://ntrs.nasa.gov/citations/19840008978) by the courtesy of NASA\n", "\n", "In quantum mechanics, wave function collapse occurs when a wave function—initially in a superposition of several eigenstates—reduces to a single eigenstate due to interaction with the external world, such as when we are making an observation.\n", "\n", "In mathematics the wave function may be any square-integrable function, before collapsing and is therefore associated with the probability density of a quantum-mechanical system. This function is expressible as a linear combination of the eigenstates of any observable. Observables represent classical dynamical variables, and when one is measured by a classical observer, the wave function is projected onto a random eigenstate of that observable. The observer simultaneously measures the classical value of that observable to be the eigenvalue of the final state.\n", "\n", "Wave function collapse can be employed as a computational technique used in procedural generation to generate complex and non-repetitive patterns or structures. This algorithmic method utilizes probability distributions to determine the appearance and placement of different elements within a generated environment. It is based on the Model Synthesis Algorithm.\n", "\n", "**Computational techniques**\n", "\n", "The process starts with a small seed pattern, which is then expanded iteratively by selecting and \"collapsing\" the probabilities of neighboring elements until the entire structure is complete. The algorithm ensures that the resulting output is unique and non-repetitive by collapsing the probabilities in such a way that neighboring elements are always compatible with each other [Gumin, Maxim (2016)](https://github.com/mxgmn/WaveFunctionCollapse). The compatibility of the neighbors acts as a constraint that is solved using constraint propagation. In this way, wave function collapse is used to create intricate and realistic environments for video games, simulations, and other applications. The algorithm is highly customizable and can be adapted to different types of environments, textures, and patterns, making it an extremely versatile tool for procedural generation\n", "\n", "**Optimization**\n", "\n", "The application of the computational technique has turned out to be a very efficient method for solving discrete optimization problems:\n", "\n", "- Sudokus\n", "- Traffic jams\n", "- Path-finding (outperforming the A* algorithm)\n", "\n", "I therefore wonder if it worth diving a bit further into the topic to determine if other \"hard problems\" may be solved effectively using the same approach?\n", "\n", "For example, is it possible to arrive at the configuration illustrated below through wave function collapse?\n", "\n", "
\n", "[Source: fogleman](https://github.com/fogleman/pack3d)\n", "\n", "The objective function is to maximize the number of tugboats within the space that the 3d printer permits. Each tugboat in the image has 6 unique orientations and 6 unique rotations and depend on the orientation of the neighbours. \n", "\n", "Another combinatorial problem that has linear, and not just discrete attributes, is the continuous time scheduling problem, where tasks are to be sequenced to minimize global parameters, such as, for example total time elapsed. Each task depends on setup-, run- and teardown-time and may have dependencies to other tasks. Although the start- and end-time is in continuous time, which will lead to various offsets on the continuous scale, there are a limited number of configurations in which the schedule will be valid, and all of those configurations will depend on neighbouring states. So again: Wave function collapse could lead to a solution.\n", "\n", "Finally there is a problem that scares me a little: The traveling salesmans problem. It is commonly evaluated as setting discrete pointers to two neighbours and applies a mixture of link-swapping, edge-swapping (opt-2, opt-3 and opt-4) to determine the shortest global path. I dare to imagine an approach where the wave function collapse is used to determine the solution to the TSP, by evaluating the probabilities of edges being dominant in a mixture of simulated annealing at the level of probabilities. I honestly have no idea whether I can get it to work, but without a hypothesis there can be no thesis and antithesis.\n", "\n", "Across all of these problems, the goal is simple: Determine whether a method based on wave function collapse can outperform existing solutions." ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "language_info": { "name": "python" }, "orig_nbformat": 4 }, "nbformat": 4, "nbformat_minor": 2 }