Archive for the ‘HPC TECHNOLOGY & AND MARKET’ 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

IP. El caso CRISPR.

mayo 2, 2018

En esta entrada combinamos muy brevemente dos materias que nos interesan: la propiedad intelectual y la genetica / genomica (sobre la que hemos hablado en las recientes entradas).

Y lo hacemos muy brevemente. Con un enlace. 

Al parecer hay un problema de patentes de por medio. Cuando nos documentemos quizas ampliemos la entrada.

 

 

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…)

El computador hidraulico.

marzo 23, 2018

Seguimos con entradas cortas inspiradas por las recientes lecturas. En esta ocasion mostramos una curiosidad.

Nota. En mayo de 2017, ultimo periodo en el que tuvimos tiempo para dedicar a estos temas escribimos una entrada de contenido similar pero mucho mas detallada y con muchos mas enlaces.

En esta entrada se ve claramente como la aplicacion / motivacion principal de los implicados en el diseno de maquinas computacionales era la elaboracion de tablas: astrnomicas, balisticas, de navegacion, actuariale, censos etc…

Fin de nota.

 

1.La computacion actual esta basada en el fenomeno de la electricidad, que no es mas que un flujo de electrones.

(more…)

Lo analógico, lo digital, lo cuántico: Vannevar Bush vs. Claude Shannon vs ¿?.

marzo 15, 2018

Esta entrada va sobre tres temas entrelazados que serán aparentes (y hacemos explícitos mediante tres notas) a medida que el lector vaya avanzando.

(more…)

IP. Caso Intotally (2).

octubre 28, 2017

En 2012 hicimos una entrada sobre Intotally Top Optimized Technologies, una empresa española que estaba comercializando con éxito una tecnología ¿ patentada en EEUU o sólo en España ?. No son muchos los casos de éxito en el campo de la invención y transferencia de tecnología, sobre todo si la empresa es española.

Nota al margen. Da gusto volver a temas del siglo XXI tras un mes en el que muchos hemos estado prestando gran parte de nuestra atención a temas más propios del XIX. Fin de nota al margen.

Sinceramente ya ni me acordaba ni del caso ni del post, aunque sí del nombre de la empresa. Pero hace un par de días nos han contactado desde esta empresa facilitándonos algunos enlaces donde se informa del desenlace del caso. En esta breve entrada re-publicamos estos enlaces sin añadir mayor comentario, ya que carecemos de tiempo para ello.

La cosa ha terminado en batalla IP: resumiendo y simplificando, Intotally ha demandado a sus socios comerciales por  incumplimiento de contrato. En alianzas del tipo David-Goliath, este suele ser un final frecuente. Conozco otro caso similar de un académico-inventor, un primer espada en su campo, con el que tuve una reunión hace años.

Quiero actuar con la máxima transparencia en este tema, para que no parezca lo que no es. Por ello copio literalmente el email recibido de esta empresa tecnológica, dónde aparecen los enlaces. Sólo elimino el nombre que aparece. La fecha de recepción del email es el lunes 23 de octubre de 2017 y la de lectura el miércoles 25 de octubre de 2017. Ha habido un intercambio de emails posterior puramente “protocolario”. Hasta hoy no he tenido  tiempo para publicar la entrada.

Estimado Editor,

Soy XXXX, Consejero Delegado de ToT, le envío este mail para informarle a través de artículos de prensa de cómo ha evolucionado el caso InToTally:

El confidencial, 28-11-2016.

Expansión, 16-10-2017.

Adjunto también una imagen de un artículo de prensa.


A continuación algunos extractos de uno de los enlaces (el más reciente):

(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…)

IP. Nuevo director en la USPTO.

agosto 28, 2017

Dejemos que hable al respecto el blog que seguimos habitualmente para estos temas.

El nuevo Director, Andrei Iancu, no es la persona que ha firmado nuestra segunda patente. Ha sido el Director interino hasta su nombramiento, Joseph Mataf.