Archive for the ‘US PATENT APPLICATION RESEARCH’ Category

Algoritmica y complejidad computacional. Nuevos resultados sobre permutaciones.

mayo 21, 2018

Compilamos en esta entrada dos nuevos “resultados” relacionados con el tema de permutaciones / grafos de Cayley, resultados que hemos visto muy por encima (prácticamente solo los títulos) y tenemos que mirar en detalle.  Aparentemente están relacionados, pero ya digo que tengo que mirarlos en detalle.

1.El primero  es un resultado que al parecer resuelve un problema que estaba abierto desde hacía tiempo. Los dos artículos son los siguientes.

–Circular support in random sorting networks, by Dauvergne and Virág,

–The Archimedean limit of random sorting networks by Duncan Dauvergne.

Una entrada de un blog en la cual hablan sobre este resultado.

2.El segundo es una solicitud de patente en EEUU. Y según hemos visto también es ¿ una patente coreana ?. Con el buscador cuántico de Google a veces es complicado volver a encontrar los resultados. Como el gato, a veces aparecen (estan vivis) y a veces no (estan muertos) ¿¿¿???.  Encontrada de nuevo. Es una aplicación también, entiendo que surcoreana:고전적 프로세서 상에서 양자-유사 계산을 에뮬레이트하기 위한 퀀톤 표현

El colega inventor es Arun Majumdar, y el titular es la empresa Kyndi Inc. Hemos encontrado esta solicitud de patente pues citan a una de las nuestras en ella.

Es curioso pues nuestro resultado utilizamos una terminología (entangled / entrelazado) que se utiliza también en mecánica / computación cuántica (conjuntamente con la superposición, el entrelazado sería uno de los fenómenos puramente cuánticos que harían posible una computación más rápida en los sistemas cuánticos con respecto a los clásicos; supuestamente), pero ya decimos en la propia patente que no tiene nada que ver con nada cuantico. En nuestro caso la utilizamos pues pensamos en su momento que es una palabra descriptivamente adecuada para la propiedad que intentamos describir con ella. No obstante esto nos da una idea:  estamos pensando constituir una sociedad que se llame “The Genomic Quantum Deep Learning Blockchain S.A.” 😉

Nota. Quede claro que no estamos ironizando sobre la empresa titular de la patente. Entre sus fundadores esta uno de los pioneros de la IA no basada en Machine Learning y en la empresa proponen un enfoque menos de caja negra. Obviamente, tampoco sobre el inventor. La ironia está relacionada con lo comentado en la entrada sobre criptomonedas. Fin de nota.

En fin, no pensamos que (el examinador) nos mencione por esto en concreto. En fin, espero que tras leerla en detalle no tengamos que decir en algún momento:

“¡¡¡ Cuan tontos fuimos por no haber visto esto antes !!!”.

Quanton representation for emulating quantum-like computation on classical processors

Abstract
The Quanton virtual machine approximates solutions to NP-Hard problems in factorial spaces in polynomial time. The data representation and methods emulate quantum computing on classical hardware but also implement quantum computing if run on quantum hardware. The Quanton uses permutations indexed by Lehmer codes and permutation-operators to represent quantum gates and operations. A generating function embeds the indexes into a geometric object for efficient compressed representation. A nonlinear directional probability distribution is embedded to the manifold and at the tangent space to each index point is also a linear probability distribution. Simple vector operations on the distributions correspond to quantum gate operations. The Quanton provides features of quantum computing: superpositioning, quantization and entanglement surrogates. Populations of Quantons are evolved as local evolving gate operations solving problems or as solution candidates in an Estimation of Distribution algorithm. The Quanton representation and methods are fully parallel on any hardware.

Extractos.

    DETAILED DESCRIPTION OF THE EMBODIMENTS

  • [0069]
    Performing an approximation to quantum computing by treating permutations as representative of model states provides the interpretation that all states are simultaneously computed by iteration. Treating distributions as approximating density functionals, estimating distributions, coupling these distributions to state spaces represented by permutations, computing based on these distributions, reasoning with these distributions over the symmetric group and structure learning using the present Quanton model are the central ideas as described by embodiments of the present disclosure.
  • [0070]
    The search space of solutions in permutation problems of n items is n factorial. The search space is usually denoted as Sn, in reference to the symmetric group of size n. In general, permutation problems are known as very hard problems when n goes above a relatively small number and their computational complexity demonstrated that many of the typical permutation problems is NP-hard. In view of their complexity, computing optimal solutions is intractable in general. For this reason, invented the Quanton in order to put in place a data structure designed to work, at worst approximately, and at best in certain special cases, exactly, at the factorial sizes of the search space.
  • [0071]
    Furthermore, noting that Quantum computing also has a very large space in terms of solution possibilities, the Quanton data structure and methods, using the unique, efficient and computable model described in the present disclosure built on the idea of permutation as computation (aka permutational quantum computing), the Quanton is devised herein to emulate Quantum computing as a virtual machine.
  • [0072]
    Now, referring to FIG. 1, which provides a Quanton Overview, there are two parts to the overall procedure: first, there is the local procedure for creating the Quanton for use in emulating localized (to the Quanton) computational operations and then there is the global procedure for evolving the Quanton or a population of Quantons to learn about incoming data problems. This is done in order to produce optimal solutions based on the procedure of Estimation of Distribution (EDA) algorithms, also known as Probabilistic Model Building Genetic Algorithm (PMBGA).
  • [0073]
    The Quanton uses embeds permutations in special way that allows the permutations to each have a unique index (by using a lattice) into a continuous probability space. The produces a unique encoding for operations that enable it to mimic quantum gates. Hence quantum gates are embedded in a continuous probabilistic vector space in which fast vector computations perform the equivalent of complex quantum gate operations, transforming inputs to outputs, or, equivalently, computing quantum transitions from state to state. Given that all permutations are simultaneously available as indexed on the Quanton, every continuous vector space operation, therefore, updates all permutations simultaneously since it is the probability density distribution that is performing the update. In this sense the Quanton represents a superposition of all potential solutions. The Quanton represents quantized discrete structure because of its lattice and entanglements are represented by correlations between variables that emerge as a result of an evolutionary process that surfaces the entangled states as solution sets to the input query state (i.e. the data to be learned or solved).

….

  •  A permutation distance function is used to measure the Quantum Gate solution. If the distance is small, then a solution is near. If the distance is far, then solution is still to be found. A critical piece of the Quanton is, therefore, the choice of a permutational distance function. There are several choices for the distance functions, such as the Hamming Distance between the output bit-strings of gate operations or Levenstein Distance as an edit distance between bit strings of the gate operations. However, the disclosure uses a permutational distance that is more closely aligned with the probabilistic nature of quantum systems: the distance measurement on permutations is based on the generalized Mallows model following the teachings of J Ceberio, E Irurozki, A Mendiburu, J A Lozano, “A review of distances for the Mallows and Generalized Mallows estimation of distribution algorithms”, Computational Optimization and Applications 62 (2), 545-564 and is incorporated herein in its entirety.
  • [0085]
    The distance measure is an analog to the Levenstein Edit distance measure between strings except that in this case, The Mallows model is use which is a distance-based exponential model that uses the Kendall tau distance in analogy with the Levenstein measure: given two permutations σ1 and σ2, the measure counts the total number of pairwise disagreements between σ1 and σ2 which is equivalent to the minimum number of adjacent swaps to convert σ1 into σ2. As noted in section of the present disclosure corresponding to FIG. 39, this is actually equivalent to a Quantum Gate operator in the Quantum Permutational computation regime presented in this disclosure. Hence, the evolution, using this distance measure, seeks optimal quantum circuits performing the problem solving.

Por lo que hemos resaltado en negrita, pensamos que los dos resultados mencionados podrían estar relacionados, pero ya decimos que tenemos  que verlos los dos con mas detalle…

Actualizaremos la entrada en su momento.

Anuncios

Teoria general de las criptomonedas: economia y negocios / inversion.

mayo 5, 2018

Esta es una nueva version del texto que aparecia en la postdata de la entrada anterior. Ya dijimos que seguramente hariamos una entrada especifica y eliminariamos el texto de la parte anterior.

Seguimos trabajando en el tema sobre todo en determinados puntos mas cuantitativos. La version sera definitiva cuando eliminemos estas dos ultimas frases.

Escribimos desde el smartphone. No nos resulta comodo poner acentos y a veces el corrector juega malas pasadas. Pedimos disculpas al lector por ello.

(more…)

IP. La propiedad intelectual en el nacimiento de las computadoras contemporaneas.

marzo 24, 2018

1.Seguimos con entradas vinculadas a las lecturas recientes.

Concretamente estamos leyendo entre otros un libro titulado Historia y critica de la informatica, de Philippe Breton.

Es de 1987 y por lo tanto anterior a Internet, lo cual lo hace mas interesante.

2. Queda claro que ya en la segunda mitad de la decada de los 30 del siglo pasado se empiezas a impulsar variados proyectos de computadores basados en diversas las tecnologias que hemos comentado en la entrada anterior: Zuse y su serie Z, Atanasoff y Berry y su ABC, Aiken y su Harvard Mark 1, Stibitz y su Model 1, y el ENIAC de Eckert y Mauchly. Seguramente la lista no es exhaustiva.

Nota. Cual era la situacion del tratamiento automatico de la informacion (incluimos el calculo aritmetico o numerico) antes de estos proyectos que acabamos de citar ?.

(more…)

Complejidad computacional. Una identidad absurda.

marzo 23, 2018

1.Desconozco su origen, pero es la que al final ha calado (en el titulo nos referimos a la primera identidad de las dos siguientes):

–P = problema facil.

–NP = problema dificil.

La realidad es otra (si finalmente se confirmase en el sentido de desigualdad la conocida conjetura):

–P = problema dificil para el que existe un algoritmo inteligente en todas sus subrutinas que evita la fuerza bruta.

–NP = problema cuya verificacion evita la fuerza bruta (para lo cual se necesita tambien en ocasiones un procedimiento inteligente) pero cuya decision tiene alguna subrutina para la cual es imposible evitarla independientemente de que el resto de subrutinas se hayan pulido al maximo (se hayan encontrado procedimientos inteligentes que eviten la fuerza bruta).

En definitiva, las identidades mas adecuadas parecen ser las siguientes:

–P = Problemas Dificiles.

–NP = Problemas Imposibles.

Imposibles en el sentido de que se espera una demostracion de imposibilidad de pulir todas sus subrutinas a un estado polinomuciico, si la famosa conjetura es correcta.

Y P, mas dificil todavia, teniendo en cuenta que, en este caso tocaria pulir con inteligencia todas las subrutinas.

2. Esto explica que

(more…)

Casos 1/2 entangled: por que son problematicos.

noviembre 1, 2017

Disclaimer. Como casi siempre ultimamente publicamos esta entrada desde el smartphone. No nos es comodo.  Por ello puede contener faltas de ortografia (sobre todo acentos y ausencia de enie). Fin de disclaimer. 

Explicar esto era una asignatura pendiente. Hemos estado estudiando en detalle los casos C2C3 (queremos ver como funciona el metodo de la escalera en estos casos extremos; una primera conclusion es que en todos estos casos la region factible es muy estrecha, lo cual es logico; tambien vemos que el metodo funciona perfectamente tambien para estos casos, como no podria ser de otra manera) y nos hemos encontrado con una caso 1/2 entangled que es muy ilustrativo sobre la problematica de estos casos en general.

Nota al margen. Recordamos que el metodo de la escalera es el mas general aplicable a todos los casos, no solo a los casos de tipo C2C3. En estos casos el metodo de Milnor es aplicable y mucho mas rapido. Pero a nosotros nos interesa la generalidad. Por cierto sigo sin entender el 9 del metodo de Milnor. Fin de nota.

Una vez se ve la figura que presentamos a continuacion y se analiza con nuestro metodo se ve claramente cual es el problema. No hace falta anadir explicaciones adicionales. La figura habla por si sola.

(more…)

Otros parámetros relevantes en los casos (3,3) generados.

septiembre 24, 2017

Actualización 15 octubre 2017.

En una entrada anterior de mayo de 2016 en la que comentamos sobre una generalización al resultado de Milnor,  hacíamos el siguiente comentario.

3. ¿ No podría generalizarse esta técnica a otros casos (2-n) generalizados ?. Entiendo que como mucho a los (2-4) generados.  A partir de aquí, el tema está tan abierto que determinar los paths posibles cuando se recorres la zona en la que no se encuentra el IAS identidad, puede empezar a ser complejo. Estudiaremos los casos (2-4) generados.

En esta entrada vemos que no es el unico caso.

Fin actualización.

El teorema de Milnor sobre casos (2,3) generados, sobre el que hicimos varias entradas bastante detalladas el ano pasado (en la ultima esbozabamos una generalizacion aplicable a estos mismos casos 2,3 generados), se puede “generalizar” en otros dos sentidos: analizando casos (2,n) generados (cosa que hemos realizado tambien en anteriores entradas sobre casos 2,4 generados, 2,5 generados y 2,6 generados) o analizando casos (3,3) generados, es decir aquellos en los que los dos generadores son de orden 3.

El análisis de estos casos (3,3) generados nos hace ver que, al igual queqhay sucedia para los casos 2,3 generados, hay otros parámetros clave para determinar si existen recorridos hamiltonianos en estos casos. Es decir, el orden de los dos generadores, el orden del IAS y del DAS, el orden de la circunferencia no son suficientes.

Si los generadores son x e y, los otros dos parámetros relevantes son (xy)^n=1 y (xxyy)^n=1.

Recordamos que en los casos 2,3 generados el parametro clave era el n de la relacion (xy^2)^n=1.

El lector puede comprobarlo analizando un caso de S4 con dos generadores de orden 3, IAS6 y circunferencia 2 (y por lo tanto 1/2 entangled). El análisis de este caso es muy ilustrativo y ? seguramente ?se puede generalizar a todos los casos (3,3) generados. El tema no esta 100% claro.  Por experiencia sabemos que no conviene extrapolar demasiado lo que ocurre en casos pequenos. Lo veremos en otra entrada cuando tengamos tiempo de desarrollar el tema.

Por otra parte he visto que al igual que los casos (2,3) generados, los casos (3,3) generados han sido bastante estudiados por la teoría de grupos de principios del XX: es parte del estudio de los

grupos abstractos de tipo (l,p| q,r),

siguiendo la expresión de Coxeter. Este autor y anteriormente otros como W.A. Edington, Miller, Sinkov y otros los han estudiado.

Un artículo de principios del XXI sobre el tema:

The abstract groups (3, 3 | 3, p). 

The two-generated abstract groups (l, m | n, k) defined by presentations
(l, m | n, k) = <x, y | x^l = y^m = (xy)^n = (x^−1y)^k>i (2)
were first studied by Edington [3], for some small values of  l, m, n and k.

The notation we use was devised by Coxeter [1] and Moser [2], and has a
deeper meaning that we will not discuss here.

From now on, we will always refer to presentation (2) when speaking about (l, m | n, k).

The starting point for our discussion is Theorem 2, due to Edington [3,
Theorem IV and pp. 208210]. (Notice that there is a typo concerning the
order of (3, 3 | 3, n), and a misprint claiming that (3, 3 | 3, 3) is isomorphic
to A4.). For the convenience of the reader, we give a short, contemporary
proof.

Theorem 2 (Edington). The group G = (3, 3 | 3, n) exists for every n > 1,
is of order 3n^2, and is non-abelian when n > 1. It contains a normal
subgroup H = <x^2y, xy^2>i ∼= Cn × Cn. In particular, G ∼= C3 when n = 1,
G ∼= A4 when n = 2, and G is the unique non-abelian group of order 27 and
exponent 3 when n = 3.

(more…)

Digrafos de Cayley bigenerados: propiedades estructurales y dificultad de los casos.

agosto 30, 2017

Llevo un cierto tiempo pensando en el siguiente tema (realmente dos dias). Las diferentes propiedades estructurales que hemos identificado (entrelazado de ciclos, entrelazado y retorcimiento) son condiciones necesarias de dificultad pero no suficientes. Que son necesarias lo hemos demstrado en anteriores entradas. Que no son suficientes lo demuestra el hecho de que hay casos con las propiedades que no suponen dificultades.

(more…)

Casos smooth.

agosto 28, 2017

Ya lo hemos comentado en anteriores entradas. No tenemos tiempo para dedicarle a estos temas.

Pero si queremos mostrar un par de casos que ilustran el concepto de smooth o lisura en el entorno de la identidad. Y queremos mostrarlo con casos en los que ninguno de los generadores sean de orden 2. (more…)

HPC. Novedades investigacion.

agosto 20, 2017

Disclaimer. Escribimos la entrada desde el smartphone. Nos es complicado poner acentos. Pedimos disculpas al lector por ello.

Pocas entradas ultimamente eh ? Muchos motivos lo explican. Entre otros el smartphone, un autentico killer. Pero no solo esto.

Lamentablemente, pese a lo planificado tambien poca investigacion. Por los mismos motivos. Pero si he pensado mentalmente en algunos temas que queremos resumir muy brevemente en esta entrada y que desarrollaremos en otro momento. Lealos el lector como unas reflexiones no muy maduradas en voz alta que pueden ser incorrectas, sobre todo la parte que se refiere a los casos twisted.

(more…)

Ip. La prueba documental.

agosto 6, 2017

Por el titulo nos referimos a las pruebas documentales de la concesion de la segunda patente.

La recepcion por correo.

Y en las siguientes imagenes la primera pagina de la segunda, las portadas de las dos y las primeras paginas de las dos.